Weighted Bipartite Matching in Matrix Multiplication Time (Extended Abstract)
Piotr Sankowski · 2006
In this paper we consider the problem of finding maximum weighted matchings in bipartite graphs with nonnegative integer weights. The presented algorithm for this problem work in ˜ O( Wn ω ) 1 time, where ω is the matrix multiplication exponent, and W is the highest edge weight in the graph. As a consequence of this result we obtain ˜ O( Wn ω )t ime algorithms for computing: minimum weight bipartite vertex cover, single source shortest paths and minimum weight vertex disjoint s-t paths.