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

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.