PushrelabelMethoden

Push-Relabel-Methoden sind eine Klasse von Algorithmen zur Bestimmung des maximalen Flusses in gerichteten Flussnetzen. Im Gegensatz zu klassischen Fluss-Verfahren arbeiten sie mit einem Vorfluss (preflow), der an jedem Knoten außer der Quelle zu viel abgegebene Kapazität enthalten kann. Eine Höhenfunktion h ordnet jedem Knoten eine Höhe zu, die sicherstellt, dass Flüsse nur entlang erhöhter Höhen in das Netz geleitet werden.

Die Grundoperationen sind Push und Relabel. Ein Push transferiert Flow von einem Knoten u zu einem Nachbarn v entlang einer Kante mit Restkapazität, sofern h(u) = h(v) + 1. Der Relabel-Schritt erhöht die Höhe von u, wenn kein zulässiger Push möglich ist. Durch wiederholtes Pushen und Relabeln entsteht ein zulässiger Preflow, dessen überschüssiger Flow schrittweise in Richtung Quelle verschoben wird, bis kein Überschuss mehr vorhanden ist. Die Methode arbeitet in der Restkapazität-Darstellung (Residualgraph).

Es gibt mehrere Varianten und Optimierungen, z.B. Push-Relabel nach Front (relabel-to-front), FIFO-Strategie oder Highest-Label-Strategie (HLPP). Weiterhin werden Globalrelabeling und Gap-Heuristik eingesetzt, um die Leistung in der Praxis deutlich zu verbessern.

Historisch wurden Push-Relabel-Methoden von Andrew Goldberg und Robert Tarjan in den 1980er Jahren entwickelt und gelten als leistungsfähige Alternative zu augmentierenden Pfad-Algorithmen, insbesondere für dichte Netze. Die theoretische Worst-Case-Komplexität liegt bei O(n^3) für die Standardvariante; praktisch erreichen optimierte Implementierungen sehr gute Laufzeiten.