Strongly Polynomial Parallel Maximum Flow Revisited

Adam Karczmarz, Paweł Pilarski

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized paralle…