An analysis of the highest-level selection rule in the preflow-push max-flow algorithm

Abstract

Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level selection rule, then both the running time and the number of pushes are known to be $\text{O(n}{}^2\text{m}\text{)}$, where n is the number of nodes and m is the number of edges. We give a new proof based on a potential function argument. Potential function arguments may be preferable for analyzing preflow-push algorithms, since they are simple and generic.