Report Number: CS-TR-88-1228
Institution: Stanford University, Department of Computer Science
Title: A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network
Author: Goldberg, A. V.
Author: Tarjan, R. E.
Date: November 1988
Abstract: We propose a simple parallel algorithm for finding a blocking flow in an acyclic network. On an n-vertex, m-arc network, our algorithm runs in O(n log n) time and O(nm) space using an m-processor EREW PRAM. A consequence of our algorithm is an O(n2 (log n) 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1228/CS-TR-88-1228.pdf