Content deleted Content added
Line 1:
In [[mathematical optimization]], the '''push-relabel algorithm''' (alternatively, '''preflow-push algorithm''') is an algorithm for computing [[maximum flow]]s. 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 vertices 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]] {{nowrap|''O''(''V''<sup>2</sup>''E'')}} time complexity, which is asymptotically more efficient than the {{nowrap|''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 vertex selection rule has {{nowrap|''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 {{nowrap|''O''(''VE''
The push-relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> The idea of distance labels has led to an 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"/>
| |||