STOC2022
Edge connectivity augmentation in near-linear time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
被引用 2 次
摘要
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.