ausblenden:
Schlagwörter:
-
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.
