Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 13:43, 10 April 2014

Revision as of 14:21, 10 April 2014

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.

The '''push–relabel algorithm''' is one of the most efficient algorithms to compute a [[maximum flow problem|maximum flow]]. The general algorithm has <math>O(V^2 E)</math> time complexity, while the implementation with FIFO vertex selection rule has <math>O(V^3)</math> running time, the highest active vertex selection rule provides <math>O(V^2\sqrt{E})</math> complexity, and the implementation with [[Daniel Sleator|Sleator]]'s and [[Tarjan]]'s [[Link/cut tree|dynamic tree]] data structure runs in <math>O(V E \log(V^2/E))</math> time. Asymptotically, it is more efficient than the [[Edmonds–Karp algorithm]], which runs in <math>O(VE^2)</math> time.

The push-relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] <math>O(V^2 E)</math> time complexity, which is asymptotically more efficient than the <math>O(VE^2)</math> [[Edmonds–Karp algorithm]]. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label vertex selection rule has <math>O(V^2\sqrt{E})</math> time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic <math>O(V E \log(V^2/E))</math> time complexity can be achieved using [[Link-cut tree|dynamic trees]], although in practice it is less efficient.

==Overview==