×

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.

MSC:
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
PDF BibTeX XML Cite
Full Text: DOI