# Dynamic Matchings in Convex Bipartite Graphs

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*(log^{2}|*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* log^{2}|*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*|} log^{2}|*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)

**BIBT**_{E}X 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"
}

l>