A parallel algorithm for finding a blocking flow in an acyclic network

The authors propose a simple parallel algorithm for finding a blocking flow in an acyclic network. On an n-vertex, m-arc network, the present algorithm runs in O(n logn) time and O(nm) space using an m-processor EREW PRAM. A consequence of the algorithm is an O(n²(logn)log(nC)) time, O(nm) space, m-processor algorithm for the minimum-cost circulation problem, on a network with integer arc capacities of magnitude at most C.