Push-Relabel Algorithm

In mathematical optimization, the push-relabel algorithm, also called the preflow-push algorithm, computes maximum flows in a flow network, taking its name from its two basic operations. Throughout its execution the algorithm maintains a preflow and gradually converts it into a maximum flow by moving flow locally between neighboring nodes through push operations, guided by an admissible network maintained through relabel operations; by comparison, the Ford-Fulkerson algorithm performs global augmentations sending flow along paths from source to sink. Push-relabel is considered one of the most efficient maximum flow algorithms, with the generic version running in strongly polynomial O(V squared times E) time, more efficient than the O(V times E squared) Edmonds-Karp algorithm, and specific variants achieve even lower complexity; the variant using the highest-label selection rule runs in O(V squared times the square root of E) time and is generally regarded as the benchmark for maximum flow algorithms. The algorithm has also been extended to compute minimum cost flows.