Finding maximum flows in undirected graphs seems easier than bipartite matching
David R. Karger, Matthew S. Levine · 1998
Consider an rr-vertex, m-edge, undirected graph with maximum llow value v.We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n@) time per path.This lets us improve the time bound of the classic augmenting path algorithm to O(m + nvsi2) on simple graphs.The addition of a blocking flow subroutine gives a simple, deterministic O(nm2/3v1/6)-time algorithm, We also use our technique to improve known randomized algorithms, giving @rtr+nv5/4)-time and d(m+-nt'~gv)-time algorithms for capacitated undirected graphs.-Forsimple graphs, in which v s II, the last bound is a(n2s2), improving on the best previous bound of O(n2*5), which is also the best known time bound for bipartite matching.