Edge connectivity augmentation in near-linear time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
2022Year
2Citations
5Top-tier citations
Abstract
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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers5
- Deterministic Min-cut in Poly-logarithmic Max-flowsJason Li, Debmalya PanigrahiFOCS 2020 · 36 citations
- Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum FlowsRuoxu Cen, William He, Jason Li, Debmalya PanigrahiSODA 2023 · 3 citations
- Faster algorithms for packing forests in graphs and related problemsPavel A. Arkhipov, Vladimir KolmogorovSODA 2026 · 1 citation
- Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random ContractionChaitanya Nalam, Thatchaphol SaranurakSODA 2023
- Cactus Representation of Minimum Cuts: Derandomize and Speed upZhongtian He, Shang-En Huang, Thatchaphol SaranurakSODA 2024
Builds on4
- Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instancesJan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak et al.STOC 2021 · 61 citations
- Deterministic Min-cut in Poly-logarithmic Max-flowsJason Li, Debmalya PanigrahiFOCS 2020 · 36 citations
- Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-RaoYu Gao, Yang P. Liu, Richard PengFOCS 2021 · 34 citations
- Subcubic algorithms for Gomory-Hu tree in unweighted graphsAmir Abboud, Robert Krauthgamer, Ohad TrabelsiSTOC 2021 · 2 citations
Related papers
- Augmenting Edge Connectivity via Isolating CutsRuoxu Cen, Jason Li, Debmalya PanigrahiSODA 2022 · 7 citations
- Fully Dynamic Exact Edge Connectivity in Sublinear TimeGramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak et al.SODA 2023 · 3 citations
- Vertex connectivity in poly-logarithmic max-flowsJason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak et al.STOC 2021 · 31 citations
- Augmenting to 4-vertex connectivity is fixed-parameter tractableJohannes Carmesin, M. S. RamanujanSODA 2026 · 5 citations
- An improved approximation algorithm for the minimum k-edge connected multi-subgraph problemAnna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi ZhangSTOC 2022 · 6 citations
