What is recorded here?
Goldberg and Tarjan developed a maximum-flow method that temporarily permits excess flow at intermediate vertices, then uses local pushes and valid height labels to restore conservation and obtain a maximum feasible flow. A network can represent a transport system, a matching problem or another optimization task. Maximum flow asks how much can reach a sink while respecting edge capacities and conserving flow at intermediate vertices. Goldberg and Tarjan relaxed the conservation condition during computation: a preflow may temporarily leave excess at a vertex. A valid residual-distance labeling guides local pushes; when no push is possible, a relabel operation raises the vertex height. For the full-flow algorithm, termination removes intermediate excess and yields a maximum feasible flow. The generic bound is O(n²m) basic operations. Particular FIFO or maximum-distance implementations have O(n³) bounds; a dynamic-tree variant has the paper’s O(nm log(n²/m)) bound. These are distinct implementations, not interchangeable claims. The paper also treats parallel and distributed execution under explicit machine and message assumptions. It credits Karzanov’s earlier preflow idea and several inherited flow and dynamic-tree techniques. A minimum-cut/value-only variant may stop before restoring a complete feasible flow; that variant has a different output contract. The historical article does not establish current practical superiority over every other algorithm.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The method maintains a preflow and admissible height labels on a finite capacitated network. Intermediate excess is permitted; termination and feasibility need the prescribed push/relabel conditions. Variant-specific arithmetic complexity bounds are not arbitrary-precision or real-world throughput measurements. Parallel and later optimized implementations require their own guarantees.
Read the original work
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Andrew V. Goldberg; Robert E. Tarjan
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Goldberg–Tarjan: computing maximum flow with preflows and local push–relabel operations
Goldberg and Tarjan developed a maximum-flow method that temporarily permits excess flow at intermediate vertices, then uses local pushes and valid height labels to restore conservation and obtain a maximum feasible flow.
A network can represent a transport system, a matching problem or another optimization task. Maximum flow asks how much can reach a sink while respecting edge capacities and conserving flow at intermediate vertices. Goldberg and Tarjan relaxed the conservation condition during computation: a preflow may temporarily leave excess at a vertex. A valid residual-distance labeling guides local pushes; when no push is possible, a relabel operation raises the vertex height. For the full-flow algorithm, termination removes intermediate excess and yields a maximum feasible flow. The generic bound is O(n²m) basic operations. Particular FIFO or maximum-distance implementations have O(n³) bounds; a dynamic-tree variant has the paper’s O(nm log(n²/m)) bound. These are distinct implementations, not interchangeable claims. The paper also treats parallel and distributed execution under explicit machine and message assumptions. It credits Karzanov’s earlier preflow idea and several inherited flow and dynamic-tree techniques. A minimum-cut/value-only variant may stop before restoring a complete feasible flow; that variant has a different output contract. The historical article does not establish current practical superiority over every other algorithm.
Scientific scope
The method maintains a preflow and admissible height labels on a finite capacitated network. Intermediate excess is permitted; termination and feasibility need the prescribed push/relabel conditions. Variant-specific arithmetic complexity bounds are not arbitrary-precision or real-world throughput measurements. Parallel and later optimized implementations require their own guarantees.
People and systems
Andrew V. Goldberg; Robert E. Tarjan