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.
Original language | English (US) |
---|---|
Pages (from-to) | 265-271 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 31 |
Issue number | 5 |
DOIs | |
State | Published - Jun 12 1989 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Keywords
- Analysis of algorithms
- graph algorithms
- minimum-cost flow problem
- network flows
- parallel computing