Header menu link for other important links
Maintaining approximate maximum weighted matching in fully dynamic graphs
A. Anand, S. Baswana, M. Gupta,
Published in
Volume: 18
Pages: 257 - 266
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/8M* 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. © A. Anand, S. Baswana, M. Gupta and S. Sen.
About the journal
Published in
Open Access
Impact factor