An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

DOI10.1002/rsa.20542zbMath1330.05144arXiv1210.5999OpenAlexW2098308634WikidataQ57401408 ScholiaQ57401408MaRDI QIDQ3192373

Simi Haber, Alan M. Frieze

Publication date: 12 October 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.5999

zbMATH Keywords

random graphsfast algorithmHamilton cycles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42)

Related Items

A note on using the resistance-distance matrix to solve Hamiltonian cycle problem, An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution, A scaling limit for the length of the longest cycle in a sparse random graph, A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time

Cites Work

• On a sparse random graph with minimum degree three: likely Pósa sets are large
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Finding Hamilton cycles in sparse random graphs
• An algorithm for finding Hamilton paths and cycles in random graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Concentration for Independent Permutations
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Unnamed Item
• Unnamed Item