Improved time bounds for the maximum flow problem

Ravindra K. Ahuja, James B. Orlin, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

74 Scopus citations

Abstract

Recently, A.V. Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in O(n3) time on n-vertex networks. Incorporation of the dynamic tree data structure of D.D. Sleator and R.E. Tarjan yields a more complicated algorithm with a running time of O(nm log (n2/m)) on m-arc networks. R.K. Ahuja and J.B. Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in O(nm + n2 log U) time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of O(nm + n2 log U/log log U) is obtained by using a nonconstant scaling factor. Second, an even better bound of O(nm + n2(log U)HLF is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to O(nm log ((n/m)(log U)HLF + 2)).

Original languageEnglish (US)
Pages (from-to)939-954
Number of pages16
JournalSIAM Journal on Computing
Volume18
Issue number5
DOIs
StatePublished - 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved time bounds for the maximum flow problem'. Together they form a unique fingerprint.

Cite this