Processor-efficient implementation of a maximum flow algorithm (Q1178222)

The push-relabel method was developed by the author and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 35, No. 4, 921-940 (1988; Zbl 0661.90031)]. The Maximum Distance Discharge (MDD) algorithm is another variation of the generic push-relabel method. In this paper the author describes two parallel implementations of the MDD algorithm. Both implementations use \(p=O(\sqrt m)\) processors. The first implementation runs in \(O(n^ 2\log(2m/n+p)(\sqrt m/p))\) time using \(O(m+n \log n)\) memory. The second one uses \(O(m+n)\) amount of memory and runs in \(O(n^ 2\log n(\sqrt m/p))\) time (\(n\) and \(m\) denote the number of vertices and the number of arcs in the input network). Both implementations achieve near-optimal speedup for up to a linear number of processors.