Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm

Niklas Baumstark, Guy Blelloch, Julian Shun

Motivated by the observation that FIFO-based push-relabel algorithms are able to outperform highest label-based variants on modern, large maximum flow problem instances, we introdu…