A simple linear expected time algorithm for finding a Hamilton path
From MaRDI portal
Publication:1823260
DOI10.1016/0012-365X(89)90100-3zbMath0681.05051MaRDI QIDQ1823260
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
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