Abstract
We consider the problem of finding the minimum cost of a feasible flow in directed series-parallel networks. We allow 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. We develop, for the first time, an efficient NC algorithm to solve the min-cost flow problem on directed series-parallel networks partially solving a problem posed by Booth and Tarjan. Our algorithm takes $O(\log ^2m)$ time using $O(m/\log m)$ processors on an EREW PRAM and it is optimal with respect to Booth and Tarjan's algorithm with running time $O(m \log m)$. The algorithm owes it's efficiency to the tree contraction technique and using simple data structures for flow list manipulations as opposed to finger search trees.
Part of this paper appeared in: Proceedings of the 7th International Parallel Processing Symposium, pp. 188--192 1993
View the PostScript document.