Booth, Heather; Tarjan, Robert E. Finding the minimum-cost maximum flow in a series-parallel network. (English) Zbl 0795.90018 J. Algorithms 15, No. 3, 416-446 (1993). 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. Cited in 6 Documents MSC: 90B10 Deterministic network models in operations research 68Q25 Analysis of algorithms and problem complexity Keywords:minimum-cost maximum flow; series-parallel network; balanced search tree PDFBibTeX XMLCite \textit{H. Booth} and \textit{R. E. Tarjan}, J. Algorithms 15, No. 3, 416--446 (1993; Zbl 0795.90018) Full Text: DOI