TCS-TR-A-13-64

Date: Fri Apr 26 18:26:09 2013

Title: Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

Authors: Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, 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. It is not easy to find the number of self-avoiding walks from (0;0) to (n;n), because the number increases rapidly with the increase of n and mathematical formula for calculating it is not known. Our challenge is to develop advanced algorithmic techniques through efforts of finding the answer to the larger n. The idea of Knuth' s algorithm is so effective that it can compute the answer to n = 11 in a second and n = 21 in a few days, even though it is designed for general graphs. In this paper, we specialize it in grid graphs and maximize space and time efficiency. Our program have successfully computed the answer to n = 25, which had not known before.