On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three

2011/07/25 by Alan Frieze, Frieze, Alan
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1107.4947

Companion paper to "On a sparse random graph with minimum degree {three}: Likely Posa's sets are large"

openalex publication_date 2011/07/25 · arxiv created 2011/08/08 · arxiv updated 2011/08/09 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We describe and analyse a simple greedy algorithm \2G that finds a good 2-matching M in the random graph G=G_n,cn^{\d≥ 3} when c≥ 15. A 2-matching is a spanning subgraph of maximum degree two and G is drawn uniformly from graphs with vertex set [n], cn edges and minimum degree at least three. By good we mean that M has O(log n) components. We then use this 2-matching to build a Hamilton cycle in O(n^1.5+o(1)) time \whp.

Related

• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• A greedy algorithm for finding a large 2-matching on a random cubic graph
• Hamilton cycles in random graphs with minimum degree at least 3: an\n improved analysis
• Finding Hamilton cycles in random graphs with few queries
• An O(n) time algorithm for finding Hamilton cycles with high probability