An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs with n vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, as n tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. © 1987 Akadémiai Kiadó