Dynamic Matchings in Convex Bipartite Graphs

Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel

    Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

    Abstract

    We consider the problem of maintaining a maximum matching in a convex bipartite graph G = (V,E) under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in O(log2|V|) amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case O( min { k log2|V| + log|V|, |V| log|V|}) time, where k is the number of update operations since the last query for the same pair of vertices was made. In addition, we give an O(Vlog2V) -time amortized bound for this pair query.
    Original languageEnglish
    Title of host publicationProc. 32nd International Symposium on Mathematical Foundations of Computer Science
    EditorsLudek Kucera, Antonin Kucera
    Number of pages12
    PublisherSpringer
    Publication date2007
    Pages406-417
    DOIs
    Publication statusPublished - 2007
    Event32nd International Symposium on Mathematical Foundations of Computer Science - Providence, RI, United States
    Duration: 20 Oct 200723 Oct 2007

    Conference

    Conference32nd International Symposium on Mathematical Foundations of Computer Science
    Country/TerritoryUnited States
    CityProvidence, RI
    Period20/10/200723/10/2007
    SeriesLecture Notes in Computer Science
    Volume4708
    ISSN0302-9743

    Fingerprint

    Dive into the research topics of 'Dynamic Matchings in Convex Bipartite Graphs'. Together they form a unique fingerprint.

    Cite this