### 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(n^{2}(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

## Fingerprint Dive into the research topics of 'A parallel algorithm for finding a blocking flow in an acyclic network'. Together they form a unique fingerprint.

## Cite this

Goldberg, A. V., & Tarjan, R. E. (1989). A parallel algorithm for finding a blocking flow in an acyclic network.

*Information Processing Letters*,*31*(5), 265-271. https://doi.org/10.1016/0020-0190(89)90084-7