A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
Publication
, Journal Article
Li, J; Panigrahi, D; Saranurak, T
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
January 1, 2022
We give an n 2+o(1)-time algorithm for finding s-t min-cuts for all pairs of vertices s and T in a simple, undirected graph on n vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of tildeO(n 2.5}) by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of n.
Duke Scholars
Published In
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOI
ISSN
0272-5428
Publication Date
January 1, 2022
Volume
2022-February
Start / End Page
1124 / 1134
Citation
APA
Chicago
ICMJE
MLA
NLM
Li, J., Panigrahi, D., & Saranurak, T. (2022). A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2022-February, 1124–1134. https://doi.org/10.1109/FOCS52979.2021.00111
Li, J., D. Panigrahi, and T. Saranurak. “A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2022-February (January 1, 2022): 1124–34. https://doi.org/10.1109/FOCS52979.2021.00111.
Li J, Panigrahi D, Saranurak T. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2022 Jan 1;2022-February:1124–34.
Li, J., et al. “A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2022-February, Jan. 2022, pp. 1124–34. Scopus, doi:10.1109/FOCS52979.2021.00111.
Li J, Panigrahi D, Saranurak T. A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2022 Jan 1;2022-February:1124–1134.
Published In
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOI
ISSN
0272-5428
Publication Date
January 1, 2022
Volume
2022-February
Start / End Page
1124 / 1134