de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Cheriyan, J., & Mehlhorn, K. (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69, 239-242.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3557-8
Zusammenfassung
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 , 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.