TCS-TR-A-12-60

Date: 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:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060 0814, Japan.
Email: minato@ist.hokudai.ac.jp

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.