Abstract
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 Õ(m{1-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]. Show more
Publication status
publishedExternal links
Book title
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Pages / Article No.
Publisher
SIAMEvent
Subject
edge connectivity; data structures; dynamic graph algorithmsOrganisational unit
02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
More
Show all metadata
ETH Bibliography
yes
Altmetrics