Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2012.257.pdf
  • Filesize: 0.48 MB
  • 10 pages

Document Identifiers

Author Details

Abhash Anand
Surender Baswana
Manoj Gupta
Sandeep Sen

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.257

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.
Keywords
  • Matching
  • Dynamic Algorithm
  • Graph Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail