Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 416-446 |
Number of pages | 31 |
Journal | Journal of Algorithms |
Volume | 15 |
Issue number | 3 |
DOIs | |
State | Published - Nov 1993 |
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics