On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three

DOI10.1002/rsa.20482zbMath1314.05187arXiv1107.4947OpenAlexW2098045361WikidataQ57401421 ScholiaQ57401421MaRDI QIDQ2930057

Alan M. Frieze

Publication date: 17 November 2014

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

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

zbMATH Keywords

random graphHamilton cycle2-matchinggiven minimum degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07)

Related Items

Random Graphs with a Fixed Maximum Degree, Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis, Cores of random graphs are born Hamiltonian

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Hamilton cycles in 3-out
• Almost all graphs with 1.44n edges are 3-colorable
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• On tree census and the giant component in sparse random graphs
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• A greedy algorithm for finding a large 2‐matching on a random cubic graph