Analysis of Preflow Push Algorithms for Maximum Network Flow

The class of preflow push algorithms recently introduced by Goldberg and Tarjan for solving the maximum flow problem on a weighted digraph with n vertices and m edges is studied. Goldberg and Tarjan’s $O(n^3 )$ time bound for the highest distance preflow push algorithm is improved to $O(n^2 \sqrt m )$, and it is shown that this bound is tight by constructing a parametrized worst-case network. It is also shown that the $O(n^3 )$ time bound is tight for the FIFO preflow push algorithm, and the $O(n^2 m)$ time bound is tight for the LIFO preflow push algorithm. The maximal excess preflow push algorithm is then developed, and it is shown that it performs $O(n^2 \sqrt m )$ pushes and that this bound is tight. Based on this, the authors develop a maximum flow algorithm for the synchronous distributed model of computation that uses $O(n^2 \sqrt m )$ messages and $O(n^2 )$ time, thereby improving upon the best previously known algorithms for this model.