Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 15:05, 10 April 2014

Revision as of 15:21, 10 April 2014

Line 1:

In [[mathematical optimization]], the '''push-relabel algorithm''' (alternatively, '''preflow-push algorithm''') is an algorithm for computing [[Maximummaximum flow problem|maximum flows]]s. The name "push-relabel" comes from the two basic operations used in the algorithm. ComparedThroughout toits execution, the [[Ford–Fulkerson algorithm]], whichmaintains performa global"preflow" augmentationsand thatgradually sendconverts it into a maximum flow followingby pathsmoving fromflow thelocally sourcebetween toneighboring vertices using ''push'' operations under the sinkguidance of an admissible network maintained by ''relabel'' operations. In comparison, the push-relabel[[Ford–Fulkerson algorithm]] reliesperforms onglobal local updatesaugmentations that movesend flow betweenfollowing neighboringpaths verticesfrom 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''²''E'')}} time complexity, which is asymptotically more efficient than the {{nowrap|''O''(''VE''²)}} [[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''²{{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''²&#x200a;log&#x200a;(''V''²/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]], although in practice it is less efficient.<ref name="goldberg86"/>

The push-relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> The idea of distance labels developedhas forled to an more efficient augmenting path algorithm, which in turn can be incorporated back into the push-relabel algorithm has been used to create morea efficientvariant augmentingwith patheven algorithmshigher empirical performance.<ref name="goldberg08"/><ref name="ahuja91"/>

==Overview==