Edge connectivity augmentation in near-linear time
Publication
, Conference
Cen, R; Li, J; Panigrahi, D
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
September 6, 2022
We give an Õ(m)-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems.
Duke Scholars
Published In
Proceedings of the Annual ACM Symposium on Theory of Computing
DOI
ISSN
0737-8017
ISBN
9781450392648
Publication Date
September 6, 2022
Start / End Page
137 / 150
Citation
APA
Chicago
ICMJE
MLA
NLM
Cen, R., Li, J., & Panigrahi, D. (2022). Edge connectivity augmentation in near-linear time. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 137–150). https://doi.org/10.1145/3519935.3520038
Cen, R., J. Li, and D. Panigrahi. “Edge connectivity augmentation in near-linear time.” In Proceedings of the Annual ACM Symposium on Theory of Computing, 137–50, 2022. https://doi.org/10.1145/3519935.3520038.
Cen R, Li J, Panigrahi D. Edge connectivity augmentation in near-linear time. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2022. p. 137–50.
Cen, R., et al. “Edge connectivity augmentation in near-linear time.” Proceedings of the Annual ACM Symposium on Theory of Computing, 2022, pp. 137–50. Scopus, doi:10.1145/3519935.3520038.
Cen R, Li J, Panigrahi D. Edge connectivity augmentation in near-linear time. Proceedings of the Annual ACM Symposium on Theory of Computing. 2022. p. 137–150.
Published In
Proceedings of the Annual ACM Symposium on Theory of Computing
DOI
ISSN
0737-8017
ISBN
9781450392648
Publication Date
September 6, 2022
Start / End Page
137 / 150