# Can maximum matching algorithms be used for maximum weight matching?

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.

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

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.

• Great paper thank you! Wow linear time approximation is very impressive. – Dmitry Kamenetsky Feb 13 '19 at 10:31