Carnegie Mellon University
Browse

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

Download (303.12 kB)
journal contribution
posted on 2012-08-30, 00:00 authored by Prasad Chebolu, Alan FriezeAlan Frieze, Pall Melsted

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.

History

Publisher Statement

© ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published at http://doi.acm.org/10.1145/1734213.1734218

Date

2012-08-30

Usage metrics

    Categories

    Keywords

    Mathematical SciencesMathematical Sciences not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC