patternMinor
Can maximum matching algorithms be used for maximum weight matching?
Viewed 0 times
canmaximumusedweightalgorithmsformatching
Problem
There are two fast algorithms for maximum matching on general graphs:
-
Micali and Vazirani in $O(E\sqrt{V})$.
-
Mucha and Sankowski in $O(V^{2.376})$.
Can these be also used for maximum weighted matching on general graphs? Note that Edmonds' Blossom algorithm can be used to solve both problems.
-
Micali and Vazirani in $O(E\sqrt{V})$.
-
Mucha and Sankowski in $O(V^{2.376})$.
Can these be also used for maximum weighted matching on general graphs? Note that Edmonds' Blossom algorithm can be used to solve both problems.
Solution
Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms for maximum weight matching in general graphs.
Context
StackExchange Computer Science Q#104272, answer score: 5
Revisions (0)
No revisions yet.