Finding a Hamilton cycle fast on average using rotations and extensions

DOI10.1002/RSA.20918MaRDI QIDQ5120740zbMATH OpenOpenAlexFDO

Authors Yahav Alon, Michael Krivelevich

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

zbMATH Keywords

expected polynomial-time algorithmsHamilton cyclesrandom graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: We present an algorithm CRE, which either finds a Hamilton cycle in a graph $G$ or determines that there is no such cycle in the graph. The algorithm's expected running time over input distribution $GsimG(n,p)$ is $(1+o(1))n/p$, the optimal possible expected time, for $p=p(n)geq70n^{-frac12}$. This improves upon previous results on this problem due to Gurevich and Shelah, and to Thomason.

Recommendations

• Finding Hamilton cycles in sparse random graphs
• An algorithm for finding hamilton cycles in random directed graphs
• An algorithm for finding Hamilton paths and cycles in random graphs
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• Finding hidden hamiltonian cycles

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A simple linear expected time algorithm for finding a Hamilton path
• An algorithm for finding Hamilton paths and cycles in random graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Expected Computation Time for Hamiltonian Path problem
• Finding Hamilton cycles in random graphs with few queries
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Probability Inequalities for Sums of Bounded Random Variables
• Some simplified NP-complete graph problems

Cited in

(3)

• Expected Computation Time for Hamiltonian Path problem
• The completion numbers of Hamiltonicity and pancyclicity in random graphs
• An \(\mathcal{O}(N)\) time algorithm for finding Hamilton cycles with high probability

This page was built for publication: Finding a Hamilton cycle fast on average using rotations and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120740)