4 added 36 characters in body

While the general problem of enumerating detecting a Hamiltonian paths path or cycles cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles? Perhaps for certain kinds of k-ary n-cube graphs? I hope this question isn't too open-ended...

Update - Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube?

3 added 110 characters in body

While the general problem of enumerating Hamiltonian paths or cycles on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist? Perhaps for certain kinds of k-ary n-cube graphs? I hope this question isn't too open-ended...

Update - Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube?

2 edited tags
1