On the complexity of preflow-push algorithms for maximum-flow problems

We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n²m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n²m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n²m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.Research performed while the author was a Ph.D. student at Cornell University and was partially supported by the Ministry of Education of the Republic of Turkey through the scholarship program 1416.