24
Apr
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.
