6.9.6. Running Time Analysis

Bounding the running time of the enhanced capacity scaling algorithm involves two main steps: bounding the number of scaling phases the algorithm executes and bounding the number of flow augmentations the algorithm performs during those phases. We prove a bound of \(O(n \lg n)\) for both quantities. Since the cost of a flow augmentation is dominated by the cost of finding the shortest path along which to move flow and we use Dijkstra's algorithm to find this path, just as in the successive shortest paths and capacity scaling algorithms, the cost per flow augmentation is \(O(n \lg n + m)\). The total cost of the algorithm is thus \(O((n \lg n + m)n \lg n)\).