Skip to main content

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

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

Publication Date

September 6, 2022

Start / End Page

137 / 150