Fully dynamic matching in bipartite graphs

Aaron Bernstein, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

75 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
PublisherSpringer Verlag
Pages167-179
Number of pages13
ISBN (Print)9783662476710
DOIs
StatePublished - 2015
Externally publishedYes
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

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

Other

Other42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Country/TerritoryJapan
CityKyoto
Period7/6/157/10/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Fully dynamic matching in bipartite graphs'. Together they form a unique fingerprint.

Cite this