4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Have you checked the respective papers? Do they mention anything relevant? We expect you to first attempt to solve your question on your own by looking up the relevant background. $\endgroup$ Feb 13, 2019 at 4:31
  • $\begingroup$ I have checked and it seems like they don’t solve the weighted problem. However I don’t understand them well enough, so I decided to ask here. $\endgroup$ Feb 13, 2019 at 9:33
  • $\begingroup$ If they don't claim to solve the weighted problem, then they probably don't solve it. $\endgroup$ Feb 13, 2019 at 9:48

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Great paper thank you! Wow linear time approximation is very impressive. $\endgroup$ Feb 13, 2019 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.