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.
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
Slidesmfcs07matching.ppt (350 Kb)
BIBTEX entry
@incollection{mfcs07,
author = "Gerth Stø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"
}