Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
Abhash Anand, Surender Baswana, Manoj Gupta, Sandeep Sen · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2012
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.