zbMATH — the first resource for mathematics

Expected computation time for Hamiltonian path problem. (English) Zbl 0654.68083
One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamiltonian path problem. Our algorithm for the Hamiltonian path problem constructs or establishes the nonexistence of a Hamiltonian path. For a fixed probability p, the expected run-time of our algorithm on a random graph with n vertices and the edge probability p is O(n). The algorithm is adaptable to directed graphs.

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
Full Text: DOI