A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network

Abstract

We suppose 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. (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1988
Accession Number
ADA215113

Entities

People

  • Andrew V. Goldberg
  • Robert Tarjan

Organizations

  • Princeton University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Detection
  • Parallel Computing
  • Procedures (Computers)
  • Residuals
  • Saturation
  • Sequences
  • Splitting
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space