Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Push–relabel maximum flow algorithm
open-in-new
<p>In <a href="/facts/Mathematical_optimization/oRn8Iv5I">mathematical optimization</a>, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing <a href="/facts/Maximum_flow/aSal0FGF">maximum flows</a> in a <a href="/facts/Flow_network/k0LCoRwD">flow network</a>. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using <i>push</i> operations under the guidance of an admissible network maintained by <i>relabel</i> operations. In comparison, the <a href="/facts/Ford%25E2%2580%2593Fulkerson_algorithm/wwk3tw52">Ford–Fulkerson algorithm</a> performs global augmentations that send flow following paths from the source all the way to the sink. </p><p>The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a <a href="/facts/Strongly_polynomial/77T62gmf">strongly polynomial</a> <i>O</i>(<i>V</i> 2<i>E</i>) time complexity, which is asymptotically more efficient than the <i>O</i>(<i>VE</i> 2) <a href="/facts/Edmonds%25E2%2580%2593Karp_algorithm/GvH0Q88t">Edmonds–Karp algorithm</a>. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has <i>O</i>(<i>V</i> 2√<i>E</i>) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic <i>O</i>(<i>VE</i>log(<i>V</i> 2/<i>E</i>)) time complexity can be achieved using <a href="/facts/Link-cut_tree/lXQcEpyt">dynamic trees</a>, although in practice it is less efficient. </p><p>The push–relabel algorithm has been extended to compute <a href="/facts/Minimum_cost_flow/bkYsFJa9">minimum cost flows</a>. The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance. </p>