Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-186-88
A Parallel Algorithm for Finding A Blocking Flow in an Acyclic Network
Authors: Goldberg, Andrew V., Tarjan, Robert E.
Date:October 1988
Pages:9
Download Formats:
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.