Content deleted Content added
{{MOS|article|date=July 2025| MOS:FORMULA - avoid mixing {{tag|math}} and {{tl|math}} in the same expression}} |
|||
| (5 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Algorithm in mathematical optimization}}
{{MOS|article|date=July 2025| [[MOS:FORMULA]] - avoid mixing {{tag|math}} and {{tl|math}} in the same expression}}
In [[mathematical optimization]], the '''push–relabel algorithm''' (alternatively, '''preflow–push algorithm''') is an algorithm for computing [[maximum flow]]s 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.<ref name="clrs26"/>
The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] {{math|''O''(''V''<sup> 2</sup>''E'')}} time complexity, which is asymptotically more efficient than the {{math|''O''(''VE''<sup> 2</sup>)}} [[Edmonds–Karp algorithm]].<ref name="goldberg86"/> Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has {{math|''O''(''V''<sup> 2</sup>{{sqrt|''E''}})}} time complexity and is generally regarded as the benchmark for maximum flow algorithms.<ref name="ahuja97"/><ref name="goldberg08"/> Subcubic {{math|''O''(''VE''log(''V''<sup> 2</sup>/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]],<ref name="goldberg86"/> although in practice it is less efficient.
The push–relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> 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.<ref name="goldberg08"/><ref name="ahuja91"/>
| |||