A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs

Shawxing Kwok

Given a weighted bipartite graph $G=(L,R,E,w)$, the maximum weight matching (MWM) problem seeks to find a matching $M\subseteq E$ that maximizes the total weight $\sum_{e \in…