Enumerating Hamiltonian Cycles

Ville H. Pettersson

Abstract


A dynamic programming method for enumerating hamiltonian cycles in arbitrary graphs is presented. The method is applied to grid graphs, king's graphs, triangular grids, and three-dimensional grid graphs, and results are obtained for larger cases than previously published. The approach can easily be modified to enumerate hamiltonian paths and other similar structures.


Keywords


Hamiltonian cycles, Enumeration, Dynamic Programming

Full Text:

PDF