ISSN:
1432-0541
Keywords:
Graph theory
;
Network flows
;
Algorithms
;
Complexity
;
Maximum flow
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n 2 √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 2 √m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n 2 √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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01187018
Permalink
