Fast parametric maximum flow algorithm and applications

Giorgio Gallo, Michael D. Grigoriadis, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

394 Scopus citations

Abstract

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
Volume18
Issue number1
DOIs
StatePublished - Jan 1 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

Cite this