Title

An Efficient Parallel Algorithm For Min-Cost Flow On Directed Series-Parallel Networks

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.

Publication Date

1-1-1993

Publication Title

Proceedings of 7th International Parallel Processing Symposium, IPPS 1993

Number of Pages

188-192

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/IPPS.1993.262879

Socpus ID

84973558313 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84973558313

This document is currently not available here.

Share

COinS