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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v92599" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G=Gn, cnδ≥3</alternatives> when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9258r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />c≥10</alternatives>. A 2‐matching is a spanning subgraph of maximum degree two and G is drawn uniformly from graphs with vertex set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v92576" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />[n]</alternatives>, cn edges and minimum degree at least three. By good we mean that M has <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9256n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(logn)</alternatives> components. We then use this 2‐matching to build a Hamilton cycle in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v92553" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(n1.5+o(1))</alternatives> time w.h.p. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 443‐497, 2014