A simple linear expected time algorithm for finding a Hamilton path (Q1823260): Difference between revisions

Since the problem of finding a Hamiltonian path between two vertices of a graph, or showing that no such path exists, is NP-complete, it is natural to look for algorithms which are fast for most graphs. In [\textit{Y. Gorevich} and \textit{S. Shelah}, Expected computation time for Hamiltonian path problem and clique problem, SIAM J. Comput. 16, 486-502 (1987; Zbl 0654.68083)] an algorithm is presented which runs in expected time cn/p (c is a constant) and requires \(O(n^ 2)\) storage on a random n-vertex graph where edges appear with probability p, provided p is a constant. The paper under review presents a simpler algorithm which requires only on storage and runs in expected time cn/p if \(p\geq 12n^{-1/3}\). The algorithm is easily modified to find (or show the non-existence of) a Hamiltonian cycle with no change in the space or expected time bounds; similar modifications can be made for directed graphs.