Scaling algorithms for approximate and exact maximum weight matching

Ran Duan, Seth Pettie, Hsin-Hao Su

The {\em maximum cardinality} and {\em maximum weight matching} problems can be solved in time $\tilde{O}(m\sqrt{n})$, a bound that has resisted improvement despite decades of rese…