FINDING THE MINIMUM-COST MAXIMUM FLOW IN A SERIES-PARALLEL NETWORK

We give a fast algorithm for computing a minimum-cost maximum flow in a series-parallel network. On an m-edge network, the algorithm runs in O(m log m) time. The space needed is O(m) if only the cost of the minimum-cost flow is desired, or O(m log m) if the entire flow is needed. This space bound can be reduced to O(m log* m) without increasing the running time. The idea behind the algorithm is to represent a set of augmenting paths by a balanced search tree. © 1993 Academic Press, Inc.