A faster deterministic maximum flow algorithm

V. King, S. Rao, R. Tarjan

Research output: Contribution to journalArticlepeer-review

85 Scopus citations

Abstract

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n2 log2n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(logm/n log nn)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(nε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).

Original languageEnglish (US)
Pages (from-to)447-474
Number of pages28
JournalJournal of Algorithms
Volume17
Issue number3
DOIs
StatePublished - Nov 1994

All Science Journal Classification (ASJC) codes

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

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

Cite this