Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 14:21, 10 April 2014

Revision as of 14:33, 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 considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] <math>{{nowrap|''O''(''V^''<sup>2 E)</mathsup>''E'')}} time complexity, which is asymptotically more efficient than the <math>{{nowrap|''O''(''VE^''<sup>2)</mathsup>)}} [[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>{{nowrap|''O''(''V^''^2\sqrt{{sqrt|''E''}})</math>}} time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic <math>{{nowrap|''O''(V E \''VE''²&#x200a;log&#x200a;(''V^''²/''E''))</math>}} time complexity can be achieved using [[Link-cut tree|dynamic trees]], although in practice it is less efficient.

==Overview==