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

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(log²m) 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