×

Finding the minimum-cost maximum flow in a series-parallel network. (English) Zbl 0795.90018

Summary: 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.

MSC:

90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI