A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs

Nathaniel Lahn, Sharath Raghvendra

We give an $\tilde{O}(n^{7/5}\log (nC))$-time algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in $K_h$-minor free graphs with $h=O(1)$ and inte…