Flows in Undirected Unit Capacity Networks
Andrew V. Goldberg, Satish B. Rao · SIAM Journal on Discrete Mathematics · 1999
We describe an O(min(m,n 3/2 )m 1/2 )-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov and Even and Tarjan when $m = \omega(n^{3/2})$, and upon a randomized bound of Karger when $v = \Omega(n^{7/4}/m^{1/2})$.