Content deleted Content added
Line 1:
In [[mathematical optimization]], the '''push-relabel algorithm''' (alternatively, '''preflow-push algorithm''') is an algorithm for computing [[Maximum flow problem|maximum flows]]. The name "push-relabel" comes from the two basic operations used in the algorithm. Compared to the [[Ford–Fulkerson algorithm]], which perform global augmentations that send flow following paths from the source to the sink, the push-relabel algorithm relies on local updates that move flow between neighboring vertices.<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''<sup>2</sup> log (''V''<sup>2</sup>/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]], although in practice it is less efficient.<ref name="goldberg86"/>
==Overview==
| |||