Finding a Hamilton cycle fast on average using rotations and extensions

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

zbMATH Keywords

random graphsHamilton cyclesexpected polynomial-time algorithms

Mathematics Subject Classification ID

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