On a greedy 2‐matching algorithm and Hamilton cycles in random graphs with minimum degree at least three1. Issue 3 (27th December 2012) - Frieze, Alan
ABSTRACT We describe and analyse a simple greedy algorithm 2greedy that finds a good 2‐matching M in the random graph G=Gn, cnδ≥3 when c≥10. 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(logn) components. We then use this 2‐matching to build a Hamilton cycle in O(n1.5+o(1)) time w.h.p. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 443‐497, 2014