TCS-TR-A-12-60Date: Tue Sep 18 16:48:08 2012 Title: ZDD-Based Computation of the Number of Paths in a Graph Authors: Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato Contact:
Abstract. Counting the number of paths in a graph, for example the number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an nn grid, is not an easy problem since no mathematical formula is found and the number becomes too large to enumerate one by one except for small graphs. We have implemented software based on the ZDD technique in Knuth’s “The Art of Computer Programming” carefully so as to achieve better memory efficiency, and have succeeded in computing the exact numbers for some graphs that were not known until now. ©Copyright 2012 Authors |