Scaling Algorithms for Weighted Matching in General Graphs

Ran Duan, Seth Pettie, Hsin-Hao Su

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in $O(m\sqrt{n}\log (nN))$ time, $O(m\sqrt{n…