Push–relabel maximum flow algorithm
In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.
- Align
- encenter
- Alt
- enFinal maximum flow network graph
- enInitial flow network graph
- Border
- 1
- Caption
- enFinal maximum flow network graph
- enInitial flow network graph
- Comment
- enIn mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.
- Depiction
- Has abstract
- enIn mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink. The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial O(V 2E) time complexity, which is asymptotically more efficient than the O(VE 2) Edmonds–Karp algorithm. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has O(V 2√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic O(VElog(V 2/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient. The push–relabel algorithm has been extended to compute minimum cost flows. The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance.
- Hypernym
- Algorithm
- Image
- enPush Relabel Algoritm Example - Initial Graph.svg
- enPush-Relabel Algorithm Example - Final Network Graph.svg
- Is primary topic of
- Push–relabel maximum flow algorithm
- Label
- enPush–relabel maximum flow algorithm
- Link from a Wikipage to an external page
- www.adrian-haarbach.de/idp-graph-algorithms/implementation/maxflow-push-relabel/index_en.html
- Link from a Wikipage to another Wikipage
- 0%5D * n for in range(n)%5D
- Alexander V. Karzanov
- Amortized complexity
- Andrew V. Goldberg
- Breadth-first search
- C (programming language)
- Category:Graph algorithms
- Category:Network flow problem
- Edmonds–Karp algorithm
- FIFO (computing and electronics)
- File:Push-Relabel Algorithm Example - Step 1.svg
- File:Push-Relabel Algorithm Example - Step 2.svg
- File:Push-Relabel Algorithm Example - Step 3.svg
- File:Push-Relabel Algorithm Example - Step 4.svg
- File:Push-Relabel Algorithm Example - Step 5.svg
- File:Push-Relabel Algorithm Example - Step 6.svg
- File:Push-Relabel Algorithm Example - Step 7.svg
- File:Push-Relabel Algorithm Example - Step 8.svg
- File:Push-Relabel Algorithm Example - Step 9.svg
- Flow network
- Ford–Fulkerson algorithm
- Link-cut tree
- Mathematical optimization
- Max-flow min-cut theorem
- Maximum flow
- Minimum cost flow
- Potential method
- Python (programming language)
- Robert Tarjan
- Strongly polynomial
- Topological sorting
- Uzi Vishkin
- SameAs
- 2PZSU
- Algorytm push-relabel
- Goldberg-Tarjan-Algorithmus
- Goldbergův algoritmus
- m.09cr90
- Push-relabel algoritam maksimalnog protoka grafa
- Q25423274
- Q583889
- réétiquetage
- Алгоритм проталкивания предпотока
- الگوریتم Goldberg و Tarjan
- الگوریتم ارسال-برچسب
- ขั้นตอนวิธีการผลักดัน - ติดป้ายใหม่
- Subject
- Category:Graph algorithms
- Category:Network flow problem
- Thumbnail
- Title
- enC implementation
- enPython implementation
- Titlestyle
- entext-align:center
- WasDerivedFrom
- Push–relabel maximum flow algorithm?oldid=1109375636&ns=0
- Width
- 350
- WikiPageLength
- 35860
- Wikipage page ID
- 3444072
- Wikipage revision ID
- 1109375636
- WikiPageUsesTemplate
- Template:!
- Template:'
- Template:(
- Template:)
- Template:=
- Template:Clear
- Template:Hidden begin
- Template:Hidden end
- Template:Main
- Template:Math
- Template:Multiple image
- Template:Mvar
- Template:Optimization algorithms
- Template:Reflist
- Template:Sqrt
