Skip to main content

Deterministic min-cut in poly-logarithmic max-flows

Publication ,  Conference
Li, J; Panigrahi, D
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
November 1, 2020

We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m{1+ epsilon}) plus polylog (n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of tilde{O}(m cdot min(sqrt{m}, n{2/3})) for weighted graphs, and m{4/3+o(1)} for unweighted (multi)-graphs. This is the first improvement in the running time of deterministic algorithms for the min-cut problem on general (weighted/multi) graphs since the early 1990s when a running time bound of tilde{O}(mn) was established for this problem.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

November 1, 2020

Volume

2020-November

Start / End Page

85 / 92
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, J., & Panigrahi, D. (2020). Deterministic min-cut in poly-logarithmic max-flows. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (Vol. 2020-November, pp. 85–92). https://doi.org/10.1109/FOCS46700.2020.00017
Li, J., and D. Panigrahi. “Deterministic min-cut in poly-logarithmic max-flows.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2020-November:85–92, 2020. https://doi.org/10.1109/FOCS46700.2020.00017.
Li J, Panigrahi D. Deterministic min-cut in poly-logarithmic max-flows. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2020. p. 85–92.
Li, J., and D. Panigrahi. “Deterministic min-cut in poly-logarithmic max-flows.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2020-November, 2020, pp. 85–92. Scopus, doi:10.1109/FOCS46700.2020.00017.
Li J, Panigrahi D. Deterministic min-cut in poly-logarithmic max-flows. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2020. p. 85–92.

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

November 1, 2020

Volume

2020-November

Start / End Page

85 / 92