A simple linear expected time algorithm for finding a Hamilton path

DOI10.1016/0012-365X(89)90100-3zbMath0681.05051MaRDI QIDQ1823260

Andrew G. Thomason

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items

An algorithm for finding Hamilton paths and cycles in random graphs ⋮ Parallel algorithms for finding Hamilton cycles in random graphs ⋮ Finding a Hamilton cycle fast on average using rotations and extensions ⋮ A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time

Cites Work

• Unnamed Item
• Unnamed Item
• How many random edges make a graph Hamiltonian?
• An algorithm for finding Hamilton paths and cycles in random graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Relationships between nondeterministic and deterministic tape complexities
• A note on Hamiltonian circuits
• A Dynamic Programming Approach to Sequencing Problems
• Expected Computation Time for Hamiltonian Path problem
• Paths, Trees, and Flowers
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• The NP-completeness column: An ongoing guide