DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.257

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Authors: Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching M whose weight is at least 1/8 M^{*} where M^{*} is the weight of the maximum weight matching. The algorithm achieves an expected amortized O(log n log C) time per edge insertion or deletion, where C is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph.

Cite as

Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 257-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.FSTTCS.2012.257,
  author =	{Anand, Abhash and Baswana, Surender and Gupta, Manoj and Sen, Sandeep},
  title =	{{Maintaining Approximate Maximum Weighted Matching in Fully  Dynamic Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{257--266},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.257},
  URN =		{urn:nbn:de:0030-drops-38648},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.257},
  annote =	{Keywords: Matching, Dynamic Algorithm, Graph Algorithm}
}

Search Results

Documents authored by Anand, Abhash

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message