Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
Pall Melsted , CMU
April 25, 2008, 3:30PM, Wean 7220

Abstract:
We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

This is joint work with Prasad Chebolu and Alan Frieze