TY - GEN
T1 - An efficient parallel algorithm for min-cost flow on directed series-parallel networks
AU - Jain, A.
AU - Chandrasekharan, N.
N1 - Publisher Copyright:
© 1993 IEEE.
PY - 1993
Y1 - 1993
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84973558313&partnerID=8YFLogxK
U2 - 10.1109/IPPS.1993.262879
DO - 10.1109/IPPS.1993.262879
M3 - Conference contribution
AN - SCOPUS:84973558313
T3 - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
SP - 188
EP - 192
BT - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th International Parallel Processing Symposium, IPPS 1993
Y2 - 13 April 1993 through 16 April 1993
ER -