2026-07-22T06:23:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3864 2024-03-06T10:34:33Z ddc:004 open_access

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs Anand, Abhash Baswana, Surender Gupta, Manoj Sen, Sandeep Matching Dynamic Algorithm Graph Algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhash Anand and Surender Baswana and Manoj Gupta and Sandeep Sen 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.257 urn:nbn:de:0030-drops-38648 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.257 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode