10.1184/R1/6478631.v1
Alan Frieze
Alan
Frieze
On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three
Carnegie Mellon University
2012
Random Graphs
Hamilton Cycles
2-Matching Algorithm
Greedy Algorithm
2012-12-12 00:00:00
Journal contribution
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
<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>