Augmenting Edge Connectivity via Isolating Cuts

Conference Paper

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 Authors

Cited Authors

  • Cen, R; Li, J; Panigrahi, D

Published Date

  • January 1, 2022

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 2022-January /

Start / End Page

  • 3237 - 3252

International Standard Book Number 13 (ISBN-13)

  • 9781611977073

Citation Source

  • Scopus