Max flows in O(nm) time, or better
Will Devanny
We present improved polynomial time algorithms for the max flow problem
defined on a network with n nodes and m arcs. We show how
to solve the max flow problem in O(nm) time, improving upon the
best previous algorithm due to King, Rao, and Tarjan, who
solved the max flow problem in
O(nm logm/(n log n) n)
time. In the case that m = O(n), we
improve the running time to O(n2/log n).
We further improve the running time in the case that
U* = Umax/Umin
is not too large, where Umax denotes the largest
finite capacity and Umin denotes the smallest non-zero
capacity. If
log(U*) = O(n1/3 log−3 n),
we show how to solve the max flow problem in
O(nm/log n) steps.
In the case that
log(U*) = O(logk n)
for some fixed positive integer k, we show how to solve the
max flow problem in Õ(n8/3) time. This latter
algorithm relies on a subroutine for fast matrix multiplication.
(Based
on a
preprint by James B. Orlin.)