License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.227
URN: urn:nbn:de:0030-drops-48453
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4845/
Go to the corresponding LIPIcs Volume Portal

Gupta, Manoj

Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time

pdf-format:
21.pdf (0.5 MB)

Abstract

A sparse subgraph G' of G is called a matching sparsifier if the size or weight of matching in G' is approximately equal to the size or weight of maximum matching in G. Recently, algorithms have been developed to find matching sparsifiers in a static bipartite graph. In this paper, we show that we can find matching sparsifier even in an incremental bipartite graph.

This observation leads to following results: 1. We design an algorithm that maintains a (1+epsilon) approximate matching in an incremental bipartite graph in O(log^2(n) / (epsilon^{4}) update time. 2. For weighted graphs, we design an algorithm that maintains (1+epsilon) approximate weighted matching in O((log(n)*log(n*N)) / (epsilon^4) update time where \maxweight is the maximum weight of any edge in the graph.

BibTeX - Entry

@InProceedings{gupta:LIPIcs:2014:4845,
  author =	{Manoj Gupta},
  title =	{{Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{227--239},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4845},
  URN =		{urn:nbn:de:0030-drops-48453},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.227},
  annote =	{Keywords: Graph Algorithm, Dynamic Graph}
}

Keywords: Graph Algorithm, Dynamic Graph
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI