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