Finding a Hamilton cycle fast on average using rotations and extensions
From MaRDI portal
Publication:5120740
DOI10.1002/rsa.20918zbMath1453.68118arXiv1903.03007OpenAlexW3012358504MaRDI QIDQ5120740
Michael Krivelevich, Yahav Alon
Publication date: 16 September 2020
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.03007
Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- An algorithm for finding Hamilton paths and cycles in random graphs
- Hamiltonian circuits in random graphs
- Some simplified NP-complete graph problems
- A simple linear expected time algorithm for finding a Hamilton path
- Finding Hamilton cycles in random graphs with few queries
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Expected Computation Time for Hamiltonian Path problem
- Probability Inequalities for Sums of Bounded Random Variables
This page was built for publication: Finding a Hamilton cycle fast on average using rotations and extensions