A Synchronous Parallel Max-Flow Algorithm for Real-World Networks

We study computing maximum flows for real-world networks. In contrast to prior studies, our implementation is bulk synchronous. Our algorithm applies push and relabel operations on all active vertices in parallel, and maintains a preflow through a delayed flow update approach with handshakes between flow pushing and flow receiving. In our implementation the heuristics are no longer entangled with the push and relabel operations as in prior implementations. We apply two heuristics well known for the sequential algorithm, that is, global relabel and gap relabel, to our parallel implementation. Experiments on networks constructed for computer vision images show that our parallel implementation on the target 8-core machine is up to 8.6 times faster than the best sequential implementation. We also propose a new augmenting path based heuristic for small-world graphs. On large social networks with up to billions of edges our implementation achieves close to 40 times parallel speedup.