Computer Science – Artificial Intelligence
Scientific paper
2011-05-27
Journal Of Artificial Intelligence Research, Volume 9, pages 219-245, 1998
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.512
Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian Cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.
Culberson Joseph
Vandegriend B.
No associations
LandOfFree
The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664316