An efficient parallel algorithm for min-cost flow on directed series-parallel networks

A. Jain, N. Chandrasekharan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

The authors consider the problem of finding the minimum cost of a feasible flow in directed series-parallel networks with real-valued lower and upper bounds for the flows on edges. While strongly polynomial-time algorithms are known for this problem on arbitrary networks, it is known to be 'hard' for parallelization. The authors develop, for the first time, an NC algorithm to solve the min-cost flow problem on directed series-parallel networks, solving a problem posed by H. Booth (1990). The authors algorithm takes O(log2m) time using O(m/log m) processors on an EREW PRAM and it is optimal with respect to Booth's algorithm with running time O(m log m). Their algorithm owes its efficiency to the tree contraction technique and the use of simple data structures as opposed to Booth's finger search trees.

Original languageEnglish
Title of host publicationProceedings of 7th International Parallel Processing Symposium, IPPS 1993
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages188-192
Number of pages5
ISBN (Electronic)0818634421, 9780818634420
DOIs
StatePublished - 1993
Event7th International Parallel Processing Symposium, IPPS 1993 - Newport, United States
Duration: 13 Apr 199316 Apr 1993

Publication series

NameProceedings of 7th International Parallel Processing Symposium, IPPS 1993

Conference

Conference7th International Parallel Processing Symposium, IPPS 1993
Country/TerritoryUnited States
CityNewport
Period13/04/9316/04/93

Fingerprint

Dive into the research topics of 'An efficient parallel algorithm for min-cost flow on directed series-parallel networks'. Together they form a unique fingerprint.

Cite this