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.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics