|
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.
==DefinitionsKey Concepts==
<math>G(V,E)</math> is a finite [[directed graph]] in which every [[edge (graph theory)|edge]] <math>\ (u,v) \in E</math> has a non-negative, real-valued capacity <math>\ c(u,v)</math>. If <math>\ (u, v) \not \in E</math>, we assume that <math>\ c(u, v) = 0</math>. We distinguish two vertices: a source <math>\ s</math> and a sink <math>\ t</math>. A flow in a flow network is a [[real number|real]] [[function (mathematics)|function]] <math>\ f:V \times V \rightarrow \mathbb{R}</math> with the following three properties for all nodes <math>\ u</math> and <math>\ v</math>:
:{|
| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v)</math>. The flow along an edge cannot exceed its capacity.
|-
| '''Skew symmetry''': || <math>\ f(u,v) = - f(v,u)</math>. The net flow from <math>\ u</math> to <math>\ v</math> must be the opposite of the net flow from <math>\ v</math> to <math>\ u</math> (see example).
|-
| '''Flow conservation''': || <math>\ \sum_{w \in V} f(u,w) = 0</math>, unless <math>\ u=s</math> or <math>\ u=t</math>. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
|}
In a flow network, flow going into a vertex must equal flow going out of a vertex (with
|
