A computational study of the capacity scaling algorithm for the maximum flow problem

The capacity scaling algorithm for the maximum flow problem runs in O(nmlogU) time where n is the number of nodes, m is the number of arcs, and U is the largest arc capacity in the network. The two-phase capacity scaling algorithm reduces this bound to O(nmlog(U/n)). This running time is achieved with the restriction that flows are pushed on individual arcs while paths are being identified, but this causes slower empirical run times compared to the single-phase capacity scaling algorithm. In this research, we prove that the two-phase algorithm runs in the same theoretical time without the mentioned restriction. We also show that in practice, it runs significantly faster than the single-phase capacity scaling algorithm.