An O(n²log n) parallel max-flow algorithm

Abstract

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is O( n3 (log n) p), where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n3) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view. © 1982.