TY - GEN
T1 - Fully dynamic matching in bipartite graphs
AU - Bernstein, Aaron
AU - Stein, Cliff
N1 - Funding Information:
A. Bernstein—Supported in part by an NSF Graduate Fellowship and a Simons Foundation Graduate Fellowship.
Funding Information:
C. Stein—Supported in part by NSF grants CCF-1349602 and CCF-1421161.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - We present two fully dynamic algorithms for maximum cardinality matching in bipartite graphs. Our main result is a deterministic algorithm that maintains a (3/2 + ɛ) approximation in worst-case update time O(m1/4ɛ−2.5). This algorithm is polynomially faster than all previous deterministic algorithms for any constant approximation, and faster than all previous algorithms (randomized included) that achieve a better-than-2 approximation. We also give stronger results for bipartite graphs whose arboricity is at most α, achieving a (1+ɛ) approximation in worst-case update time (Formula Presented.) for constant ɛ. Previous results for small arboricity graphs had similar update times but could only maintain a maximal matching (2-approximation). All these previous algorithms, however, were not limited to bipartite graphs.
AB - We present two fully dynamic algorithms for maximum cardinality matching in bipartite graphs. Our main result is a deterministic algorithm that maintains a (3/2 + ɛ) approximation in worst-case update time O(m1/4ɛ−2.5). This algorithm is polynomially faster than all previous deterministic algorithms for any constant approximation, and faster than all previous algorithms (randomized included) that achieve a better-than-2 approximation. We also give stronger results for bipartite graphs whose arboricity is at most α, achieving a (1+ɛ) approximation in worst-case update time (Formula Presented.) for constant ɛ. Previous results for small arboricity graphs had similar update times but could only maintain a maximal matching (2-approximation). All these previous algorithms, however, were not limited to bipartite graphs.
UR - http://www.scopus.com/inward/record.url?scp=84950129650&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84950129650&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-47672-7_14
DO - 10.1007/978-3-662-47672-7_14
M3 - Conference contribution
AN - SCOPUS:84950129650
SN - 9783662476710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 167
EP - 179
BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
A2 - Halldorsson, Magnus M.
A2 - Kobayashi, Naoki
A2 - Speckmann, Bettina
A2 - Iwama, Kazuo
PB - Springer Verlag
T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Y2 - 6 July 2015 through 10 July 2015
ER -