A decomposition theorem for maximum weight bipartite matchings (Q2719128)

Let \(G\) be a bipartite graph on \(n\) vertices with integer weights (bounded by \(N\)) on the edges. Let \(W\) be the total weight of \(G\). The authors give an \(O(\sqrt{n}W\log(n^2N/W)/(\log n))\) algorithm for finding a maximum weight matching in \(G\) and claim that their algorithm has the same time complexity as the best known algorithm for finding a maximum cardinality matching. They also give an \(O(W)\) algorithm for what they call the all-cavity matching problem. Given a maximum weight matching in \(G\), it finds a maximum weight matching of \(G\setminus\{v\}\) for all vertices \(v\) of \(G\).