Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Gupta, Manoj http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-48453
URL:

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

pdf-format:


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
Seminar: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI