Fully dynamic matching in bipartite graphs

Aaron Bernstein; Cliff Stein

doi:10.1007/978-3-662-47672-7_14

Fully dynamic matching in bipartite graphs

Aaron Bernstein, Cliff Stein

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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(m^1/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.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
Editors	Magnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
Publisher	Springer Verlag
Pages	167-179
Number of pages	13
ISBN (Print)	9783662476710
DOIs	https://doi.org/10.1007/978-3-662-47672-7_14
State	Published - 2015
Event	42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan Duration: Jul 6 2015 → Jul 10 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9134
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Country/Territory	Japan
City	Kyoto
Period	7/6/15 → 7/10/15

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-47672-7_14

Cite this

Bernstein, A., & Stein, C. (2015). Fully dynamic matching in bipartite graphs. In M. M. Halldorsson, N. Kobayashi, B. Speckmann, & K. Iwama (Eds.), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings (pp. 167-179). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134). Springer Verlag. https://doi.org/10.1007/978-3-662-47672-7_14

Fully dynamic matching in bipartite graphs. / Bernstein, Aaron; Stein, Cliff.
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. ed. / Magnus M. Halldorsson; Naoki Kobayashi; Bettina Speckmann; Kazuo Iwama. Springer Verlag, 2015. p. 167-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bernstein, A & Stein, C 2015, Fully dynamic matching in bipartite graphs. in MM Halldorsson, N Kobayashi, B Speckmann & K Iwama (eds), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9134, Springer Verlag, pp. 167-179, 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan, 7/6/15. https://doi.org/10.1007/978-3-662-47672-7_14

Bernstein A, Stein C. Fully dynamic matching in bipartite graphs. In Halldorsson MM, Kobayashi N, Speckmann B, Iwama K, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Springer Verlag. 2015. p. 167-179. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-47672-7_14

Bernstein, Aaron ; Stein, Cliff. / Fully dynamic matching in bipartite graphs. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. editor / Magnus M. Halldorsson ; Naoki Kobayashi ; Bettina Speckmann ; Kazuo Iwama. Springer Verlag, 2015. pp. 167-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0f5156b8f77745f6b5cf52347b2e8f97,

title = "Fully dynamic matching in bipartite graphs",

abstract = "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.",

author = "Aaron Bernstein and Cliff Stein",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 ; Conference date: 06-07-2015 Through 10-07-2015",

year = "2015",

doi = "10.1007/978-3-662-47672-7_14",

language = "English (US)",

isbn = "9783662476710",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "167--179",

editor = "Halldorsson, {Magnus M.} and Naoki Kobayashi and Bettina Speckmann and Kazuo Iwama",

booktitle = "Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings",

}

TY - GEN

T1 - Fully dynamic matching in bipartite graphs

AU - Bernstein, Aaron

AU - Stein, Cliff

N1 - 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 -

Fully dynamic matching in bipartite graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this