A Fast Max Flow Algorithm

Understand

In 2013, Orlin proved that the max flow problem could be solved in $O(nm)$ time.

• His algorithm ran in $O(nm + m^{1.94})$ time, which was the fastest for graphs with fewer than $n^{1.06}$ arcs.
• If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan.
• We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al.