An Analysis of the Highest-level Selection rule in the Preflow-push Max-flow 
Algorithm

Cheriyan, Joseph; Mehlhorn, Kurt

doi:10.1016/S0020-0190(99)00019-8

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

An Analysis of the Highest-level Selection rule in the Preflow-push Max-flow Algorithm

MPS-Authors

/persons/resource/persons45021

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Cheriyan, J., & Mehlhorn, K. (1999). An Analysis of the Highest-level Selection rule in the Preflow-push Max-flow Algorithm. Information Processing Letters, 69(5), 239-242. doi:10.1016/S0020-0190(99)00019-8.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3557-8

Abstract

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.