Maximum weight bipartite matching in matrix multiplication time

AbstractIn 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 Õ(Wnω)11Õ denotes the so-called “soft O” notation, i.e. f(n)=Õ(g(n)) iff f(n)=O(g(n)logkn) for some constant k. 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 Õ(Wnω) 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