Seminar by Manoj Gupta

Seminar by Manoj Gupta

Fully Dynamic (1+ε) -Approximate Matchings

Manoj Gupta
IIT Delhi

    Date:    Monday, March 14th, 2013
    Time:    5:15 PM
    Venue:   CS101.

Abstract:

We present data structures that maintain approximate maximum matchings in graphs under edge insertions/deletions. Our main result is a data structure that maintains a matching whose size is at least (1-ε) of the maximum in worst case O(mε-2) per edge update. It is the first data structure that's able to maintain arbitrary quality approximations on sparse graphs in sublinear time per update. Our results of maximum cardinality matching easily extend to maximum weighted matching.

Back to Research-I Seminars