Theory Seminar 2008-04-25

April 24, 2008 at 20:11 · Maverick Woo · Filed under Calendar

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.

RSS feed | Trackback URI

Comments »

No comments yet.

Name
E-mail
URI
Your Comment (smaller size | larger size)
You may use <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong> in your comment. Your comment will be held for moderation. You will not see it immediately.