Goldberg & Tarjan: So finden Sie einen blockierenden Fluss in einem Diagramm

Ich möchte den Goldberg & Rao-Algorithmus implementieren, um einen Maxflow in einem Diagramm zu finden. Mein Problem ist der Aktualisierungsschritt, in dem in jedem Papier und Bericht angegeben ist: "Suchen Sie in der resultierenden Grafik einen blockierenden Fluss oder einen Wertfluss Delta." Sie alle beziehen sich auf Goldberg & Tarjan, um einen blockierenden Fluss zu finden. Es gibt zwei Dinge, die ich nicht verstehe:

1. Wie soll ich einen Wertefluss Delta finden?
2. Aber was noch wichtiger ist: Wie finde ich einen blockierenden Fluss?

Zu Frage 2: Ich habe die beiden Artikel gelesen (der von Goldberg & Tarjan "Ein neuer Ansatz für das Maximum-Flow-Problem" und der über dynamische Bäume - beide waren nicht so schwer zu verstehen). Jedes Papier / Bericht / Buch über Goldberg & Rao bezieht sich auf das Papier von Goldberg & Tarjan und hebt hervor, dass Goldberg & Rao nicht den Push / Relabel-Algorithmus verwenden, sondern blockierende Flüsse finden. Aber meiner Meinung nach erklärt Tarjan nur den Push / Relabel-Algorithmus. Ich kann nichts über das Blockieren von Flows finden.

T. Cormen, "Einführung in Algorithmen", 3. Auflage

Der bisher asymptotisch schnellste Algorithmus für das Maximum-Flow-Problem von Goldberg und Rao läuft in der Zeit , wobei . Dieser Algorithmus verwendet nicht die Push-Relabel-Methode, sondern basiert auf dem Auffinden blockierender Flüsse.$O(min(V^{2/3}, E^{1/2}) E \lg{(V^2/E + 2)} * \lg{C})$$C = \max c(u,v)$

A. Goldberg & S. Rao, "Beyond the Flow Decomposition Barrier" (das Originalpapier)

Unter Verwendung des Blockierungsflussalgorithmus von Goldberg und Tarjan [1988] erhalten wir eine $O (\Lambda m log(n^2/m)\log{U})$ -Bindung.

Sie haben aus irgendeinem Grund den falschen Hinweis gegeben, wie Sie selbst herausgefunden haben.

Die Blockierungsmethode, die Sie verwenden sollen, ist die in

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf , Abschnitt 8.3.