Max flows in O(nm) time, or better

In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m 31/16 log 2 n) time. In the case that m = O(n 1.06 ), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm log m/(n log n) n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n 2 / log n).

Authors

• James B. Orlin

Keywords

• max flows
• maximum flow problem