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

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)265-271
Number of pages7
JournalInformation Processing Letters
Volume31
Issue number5
DOIs
StatePublished - 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