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

摘要

We describe and analyse a simple greedy algorithm 2greedy that finds a good 2-matching M in the random graph G = G_(n,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(log n) components. We then use this 2-matching to build a Hamilton cycle in O(n~(1.5+o(1))) time w.h.p.