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: https://drops.dagstuhl.de/opus/volltexte/2014/4845/
Gupta, Manoj
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: | 12.12.2014 |
