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(√|V| log2 |V|)-time amortized bound for this pair query. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-74456-6_37 | MFCS |
Keywords | Field | DocType |
sub-linear time,amortized time,dynamic matchings,convex bipartite graph,worst-case o,maximum matching,constant worst-case time,amortized sense,k log2,last query,data structure,update operation,bipartite graph,linear time | Discrete mathematics,Combinatorics,Vertex (geometry),Amortized analysis,Bipartite graph,Convex bipartite graph,Neighbourhood (graph theory),Matching (graph theory),3-dimensional matching,Mathematics,Blossom algorithm | Conference |
Volume | ISSN | ISBN |
4708 | 0302-9743 | 3-540-74455-X |
Citations | PageRank | References |
8 | 0.59 | 15 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gerth Stølting Brodal | 1 | 1399 | 86.30 |
Loukas Georgiadis | 2 | 250 | 22.75 |
Kristoffer Arnsfelt Hansen | 3 | 176 | 21.40 |
Irit Katriel | 4 | 176 | 13.72 |