Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:41, 26 November 2013

Revision as of 20:45, 26 November 2013

Line 88:

===Push–relabel algorithm===

The generic ''Push–relabel algorithmsalgorithm'' in general havehas the following layoutstructure:

Algorithm Push-relabel(G(V,E),s,t)

# As long as there is legal ''push'' or ''relabel'' operation

while ''push'' or ''relabel'' are legal: //in other words while there is excess in the network

## Perform a legal push, or

## Perform a legal relabel.push, or

perform a legal relabel;

Executing these two functions in any order, so long as there remains any active vertices results in termination of the algorithm in a maximum flow. The running time for these algorithms when not observing any order to the Push and Relabel operations is <math>O(V^2 E)</math> (argument omitted). The bottleneck is the number of non-saturating pushes.