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