Edge connectivity augmentation in near-linear time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
2022年份
2被引次数
5顶会引用
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了最后一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
引用它的顶会 Paper5
- Deterministic Min-cut in Poly-logarithmic Max-flowsJason Li, Debmalya PanigrahiFOCS 2020 · 被引用 36 次
- Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum FlowsRuoxu Cen, William He, Jason Li, Debmalya PanigrahiSODA 2023 · 被引用 3 次
- Faster algorithms for packing forests in graphs and related problemsPavel A. Arkhipov, Vladimir KolmogorovSODA 2026 · 被引用 1 次
- 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
它引用的顶会 Paper4
- 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 等STOC 2021 · 被引用 61 次
- Deterministic Min-cut in Poly-logarithmic Max-flowsJason Li, Debmalya PanigrahiFOCS 2020 · 被引用 36 次
- Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-RaoYu Gao, Yang P. Liu, Richard PengFOCS 2021 · 被引用 34 次
- Subcubic algorithms for Gomory-Hu tree in unweighted graphsAmir Abboud, Robert Krauthgamer, Ohad TrabelsiSTOC 2021 · 被引用 2 次
相关 Paper
- Augmenting Edge Connectivity via Isolating CutsRuoxu Cen, Jason Li, Debmalya PanigrahiSODA 2022 · 被引用 7 次
- Fully Dynamic Exact Edge Connectivity in Sublinear TimeGramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak 等SODA 2023 · 被引用 3 次
- Vertex connectivity in poly-logarithmic max-flowsJason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak 等STOC 2021 · 被引用 31 次
- Augmenting to 4-vertex connectivity is fixed-parameter tractableJohannes Carmesin, M. S. RamanujanSODA 2026 · 被引用 5 次
- An improved approximation algorithm for the minimum k-edge connected multi-subgraph problemAnna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi ZhangSTOC 2022 · 被引用 6 次
