Frieze, Alan On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three <p>We describe and analyse a simple greedy algorithm 2greedy that finds a good 2-matching <em>M</em> in the random graph when . A 2-matching is a spanning subgraph of maximum degree two and <em>G</em> is drawn uniformly from graphs with vertex set , <em>cn</em> edges and minimum degree at least three. By good we mean that <em>M</em> has components. We then use this 2-matching to build a Hamilton cycle in time w.h.p.</p> Random Graphs;Hamilton Cycles;2-Matching Algorithm;Greedy Algorithm 2012-12-12
    https://kilthub.cmu.edu/articles/journal_contribution/On_a_Greedy_2-Matching_Algorithm_and_Hamilton_Cycles_in_Random_Graphs_with_Minimum_Degree_at_Least_Three/6478631
10.1184/R1/6478631.v1