TY - GEN

T1 - Dynamic Matchings in Convex Bipartite Graphs

AU - Brodal, Gerth Stølting

AU - Georgiadis, Loukas

AU - Hansen, Kristoffer Arnsfelt

AU - Katriel, Irit

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

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

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

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 406

EP - 417

BT - Proc. 32nd International Symposium on Mathematical Foundations of Computer Science

A2 - Kucera, Ludek

A2 - Kucera, Antonin

PB - Springer

T2 - 32nd International Symposium on Mathematical Foundations of Computer Science

Y2 - 20 October 2007 through 23 October 2007

ER -