Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth

Arpit Agarwal, Sanjeev Khanna, Huan Li +4

We present a parallel algorithm for the $(1-\epsilon )$-approximate maximum flow problem in capacitated, undirected graphs with $n$ vertices and $m$ edges, achieving $O(ε^{-3}\text{polylog…