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
Abstract:
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.
The ACO Seminar (2011-2012)