Content deleted Content added
Line 1:
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.
==
In a flow network, flow going into a vertex must equal flow going out of a vertex (with
| |||