Dynamic Matchings in Convex Bipartite Graphs

Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer A. Hansen, and Irit Katriel

In Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, volume 4708 of Lecture Notes in Computer Science, pages 406-417. Springer Verlag, Berlin, 2007.

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(\sqrt{|V|} log2|V|)-time amortized bound for this pair query.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2007. All rights reserved.

Online version

mfcs07matching.pdf (199 Kb)

DOI

10.1007/978-3-540-74456-6_37

Slides

mfcs07matching.pdf (600 Kb), mfcs07matching.ppt (350 Kb)

BIBTEX entry

@incollection{mfcs07,
  author = "Gerth St{\o}lting Brodal and Loukas Georgiadis and Kristoffer A. Hansen and Irit Katriel",
  booktitle = "Proc. 32nd International Symposium on Mathematical Foundations of Computer Science",
  doi = "10.1007/978-3-540-74456-6_37",
  isbn = "978-3-540-74455-9",
  pages = "406-417",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Dynamic Matchings in Convex Bipartite Graphs",
  volume = "4708",
  year = "2007"
}