Finding the minimum-cost maximum flow in a series-parallel network

Heather Booth, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)416-446
Number of pages31
JournalJournal of Algorithms
Volume15
Issue number3
DOIs
StatePublished - Jan 1 1993

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Finding the minimum-cost maximum flow in a series-parallel network'. Together they form a unique fingerprint.

Cite this