Fast parametric maximum flow algorithm and applications

Giorgio Gallo, Michael D. Grigoriadis, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

470 Scopus citations


The classical maximum flow problem sometimes occurs in settings in which the arc capacities are not fixed but are functions of a single parameter, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. In this paper it is shown that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst-case time bound. Faster algorithms for a variety of combinatorial optimization problems follow from the result.

Original languageEnglish (US)
Pages (from-to)30-55
Number of pages26
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Fast parametric maximum flow algorithm and applications'. Together they form a unique fingerprint.

Cite this