A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings

Nathaniel Lahn, Sharath Raghvendra

We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartit…