Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Rauch Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff‐Nilsen · Society for Industrial and Applied Mathematics eBooks · 2023
Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ(n) worst-case update time and Õ(m1-1/16) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].