Maximum weight bipartite matching in matrix multiplication time
In this paper we consider the problem of finding maximum weight matchings in bipartite graphs with nonnegative integer weights. The presented algorithm for this problem works in O(Wn(omega))(1) time, where omega is the matrix multiplication exponent, and W is the highest edge weight in the graph. As a consequence of this result we obtain (O) over tilde (Wn(omega)) time algorithms for computing: minimum weight bipartite vertex cover, single source shortest paths and minimum weight vertex disjoint s-t paths. All of the presented algorithms are randomized and with small probability can return suboptimal solutions. (c) 2009 Elsevier B.V. All rights reserved.
matrix multiplication shortest paths matchings in graphs weighted perfect matchings