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

DOI10.1016/0020-0190(89)90084-7zbMath0688.68034OpenAlexW2057059776MaRDI QIDQ1263969

Andrew V. Goldberg, Robert Endre Tarjan

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90084-7

zbMATH Keywords

parallel computingnetwork flowsEREW PRAMminimum cost flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Theory of software (68N99)

Related Items (1)

Sequential and parallel algorithms for minimum flows.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple version of Karzanov's blocking flow algorithm
• An applicative random-access stack
• Making data structures persistent
• Termination detection for diffusing computations
• An \(O(EV\log^2V)\) algorithm for the maximal flow problem
• An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• A data structure for dynamic trees
• Finding Minimum-Cost Circulations by Successive Approximation
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Prefix Computation
• An O(n2log n) parallel max-flow algorithm
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Parallelism in random access machines

This page was built for publication: A parallel algorithm for finding a blocking flow in an acyclic network