ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

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

Tunçel, Levent

Springer

Algorithmica 11 (1994), S. 353-359

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1432-0541

Schlagwort(e): Graph theory ; Network flows ; Algorithms ; Complexity ; Maximum flow

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik , Mathematik

Notizen: 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.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01187018

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer