A faster deterministic maximum flow algorithm

V. King, S. Rao, R. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

We describe a deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time O(mn + n 2+∈), for any constant ∈. This improves upon Alon's 1989 bound of O(mn + n8/3log n) [A] and gives an O(mn) deterministic algorithm for all m > n1+∈. Thus it extends the range of m/n for which an 0{mn) algorithm is known, and matches the 1988 algorithm of Goldberg and Tarjan [GT] for smaller values of m/n.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PublisherAssociation for Computing Machinery
Pages157-164
Number of pages8
ISBN (Electronic)089791466X
StatePublished - Sep 1 1992
Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
Duration: Jan 27 1992Jan 29 1992

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129721

Other

Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
CountryUnited States
CityOrlando
Period1/27/921/29/92

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A faster deterministic maximum flow algorithm'. Together they form a unique fingerprint.

Cite this