Skip to main content

Augmenting Edge Connectivity via Isolating Cuts

Publication ,  Conference
Cen, R; Li, J; Panigrahi, D
Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
January 1, 2022

We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS '20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of Õ(m + n3/2) and improves on the previous best time of Õ(n2) (Benczúr and Karger, SODA '98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.

Duke Scholars

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 2022

Volume

2022-January

Start / End Page

3237 / 3252
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cen, R., Li, J., & Panigrahi, D. (2022). Augmenting Edge Connectivity via Isolating Cuts. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2022-January, pp. 3237–3252).
Cen, R., J. Li, and D. Panigrahi. “Augmenting Edge Connectivity via Isolating Cuts.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2022-January:3237–52, 2022.
Cen R, Li J, Panigrahi D. Augmenting Edge Connectivity via Isolating Cuts. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2022. p. 3237–52.
Cen, R., et al. “Augmenting Edge Connectivity via Isolating Cuts.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2022-January, 2022, pp. 3237–52.
Cen R, Li J, Panigrahi D. Augmenting Edge Connectivity via Isolating Cuts. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2022. p. 3237–3252.

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Publication Date

January 1, 2022

Volume

2022-January

Start / End Page

3237 / 3252