ON THE COMPLEXITY OF PREFLOW-PUSH ALGORITHMS FOR MAXIMUM-FLOW PROBLEMS

We study the maximum-flow algorithm of Goldberg and Tarjan and show th at the largest-label implementation runs in O(n2 square-root m) time. We give a new proof of this fact. We compare our proof with the earlie r work by Cheriyan and Maheswari who showed that the largest-label imp lementation of the preflow-push algorithm of Goldberg and Tarjan runs in O(n2 square-root m) time when implemented with current edges. Our p roof that the number of nonsaturating pushes is O(n2 square-root m), d ocs not rely on implementing pushes with current edges, therefore it i s true for a much larger family of largest-label implementation of the preflow-push algorithms.