Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Abstract
Whether a graph \(G = (V,E)\) is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that undergo edge insertions and deletions. While connectivity algorithms with polylogarithmic amortized update time have been known since the 90s, achieving worst-case guarantees has proven more elusive.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Distributed systems and fault tolerance
Graph Theory and Algorithms
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 6184–6198
- Publication date
- 1 January 2026
- Language
- EN