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

Andrew V. Goldberg; Robert E. Tarjan

doi:10.1016/0020-0190(89)90084-7

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

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-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(n²(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	https://doi.org/10.1016/0020-0190(89)90084-7
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

Access to Document

10.1016/0020-0190(89)90084-7

Cite this

@article{f1bc83093bef4eb5868d5be34dc82ed3,

title = "A parallel algorithm for finding a blocking flow in an acyclic network",

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.",

keywords = "Analysis of algorithms, graph algorithms, minimum-cost flow problem, network flows, parallel computing",

author = "Goldberg, \{Andrew V.\} and Tarjan, \{Robert E.\}",

note = "Funding Information: * Research partially supported by ONR Contract NOOO14-88-K-0166, NSF Preside\&d .Young Investigator Grant CCR-8858097, and IBM Faculty Development Award. Part of this work was done while the author was at AT\&T BeII Laboratories, Murray Hi\& NJ 07974, U.S.A. ** Research partiaUy supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. NOOOl4-87-K-0467.",

year = "1989",

month = jun,

day = "12",

doi = "10.1016/0020-0190(89)90084-7",

language = "English (US)",

volume = "31",

pages = "265--271",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

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

AU - Goldberg, Andrew V.

AU - Tarjan, Robert E.

N1 - Funding Information: * Research partially supported by ONR Contract NOOO14-88-K-0166, NSF Preside&d .Young Investigator Grant CCR-8858097, and IBM Faculty Development Award. Part of this work was done while the author was at AT&T BeII Laboratories, Murray Hi& NJ 07974, U.S.A. ** Research partiaUy supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. NOOOl4-87-K-0467.

PY - 1989/6/12

Y1 - 1989/6/12

N2 - 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.

AB - 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.

KW - Analysis of algorithms

KW - graph algorithms

KW - minimum-cost flow problem

KW - network flows

KW - parallel computing

UR - https://www.scopus.com/pages/publications/0024680991

UR - https://www.scopus.com/inward/citedby.url?scp=0024680991&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(89)90084-7

DO - 10.1016/0020-0190(89)90084-7

M3 - Article

AN - SCOPUS:0024680991

SN - 0020-0190

VL - 31

SP - 265

EP - 271

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this