The title says it all. I have relatively small (40-80 nodes) cubic (3-regular) planar graphs, and I have to decide their Hamiltonicity. I am aware of the fact that this task is NP-complete, but I hope for asymptotically exponential time algorithms that are nevertheless very fast for the graph size I am interested in.
+1
A:
from http://mathworld.wolfram.com/HamiltonianCycle.html : "Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork."
The paper is for sale here: http://portal.acm.org/citation.cfm?id=321850.321854
Tom Sirgedas
2010-07-06 22:08:04
+1
A:
40 nodes seems doable. You're choosing 40 of 60 edges to include.
Let's try a depth-first search.
To start, pick a vertex V. You will need to exclude exactly one of its 3 incident edges. Try these 3 possibilities one at a time. When you choose an edge to exclude, you are forcing the inclusion of 4 edges. After this, we'll call the vertices of the excluded edge "used".
If you could repeat this process 10 times, you would have chosen all 40 edges, searching only 3^10 (59049) possibilities. Of course, you'll run out of "isolated" vertices after enough edges have been determined.
But, we now have an idea for an algorithm. At each step, try picking a vertex with the fewest "used" neighbors. Actually, picking a vertex with 2 used neighbors is best, since the used edge is forced. I'm not sure if picking a vertex with 1 or 0 used neighbors is the next best. Try both ways! (And 3 used neighbors indicates a failed search)
When we're done picking edges, check if they form a single cycle.
Do you have a few sample graphs? I might try a simple implementation.
Tom Sirgedas
2010-07-06 22:51:00