3
$\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.

|cite|improve this question
$\endgroup$
  • $\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$ – Yuval Filmus Feb 13 '19 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$ – Dmitry Kamenetsky Feb 13 '19 at 9:33
  • $\begingroup$ If they don't claim to solve the weighted problem, then they probably don't solve it. $\endgroup$ – Yuval Filmus Feb 13 '19 at 9:48
4
$\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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Great paper thank you! Wow linear time approximation is very impressive. $\endgroup$ – Dmitry Kamenetsky Feb 13 '19 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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