We describe an O(min(m, n/sup 3/2/)m/sup 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=/spl omega/(n/sup 3/2/), and upon a randomized bound of Karger when /spl upsi/=/spl Omega/(n/sup 7/4//m/sup 1/2/).
['Andrew V. Goldberg', 'Satish Rao']
Flows in undirected unit capacity networks