ACO The ACO Seminar (2011-2012)

Dec 8 , 3:30pm, Wean 8220
Alan Frieze, CMU
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 that finds a good 2-matching M in a random graph G. A 2-matching is a spanning subgraph of maximum degree two and G is drawn uniformly from graphs with vertex set [n], cn (c>=15) 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.

Back to the ACO home page