Content deleted Content added
Line 2:
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"/>
The idea of distance labels developed for the push-relabel algorithm has been used to create more efficient augmenting path algorithms.<ref name="ahuja91"/>
==Overview==
| |||