Push-Relabel Algorithmus

Sind dual zu AW-Algorithmen.

Idee

So viel Fluss wie möglich auf das Flussnetzwerk schicken. Dabei darf die Flusserhaltungsbedingung verletzt werden.
Durch die Verletzung entsteht ein Überschuss, der in einem Pseudofluss aber erlaubt ist.

Wofür

Zur Vermeidung vieler Augmentierender Wege wie in diesem Fall:

Gültige Markierung
(Nicht-)Saturierte Schübe

Ein Algorithmus, der dieses Konzept verwendet ist der Goldberg–Tarjan Algorithmus.