Faster Worst Case Deterministic Dynamic Connectivity

2015/07/21 by Casper Kejlberg-Rasmussen, Kejlberg-Rasmussen, Casper, Tsvi Kopelowitz +5
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1507.05944

openalex publication_date 2015/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(√((n(loglog n)²)/(log n))) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (STOC 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM 1997), which had update time O(√(n)). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

Citations

• A note on two problems in connexion with graphs

Related

• Faster Deterministic Fully-Dynamic Graph Connectivity
• Dynamic graph connectivity with improved worst case update time and sublinear space
• Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
• Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
• An Improved Randomized Data Structure for Dynamic Graph Connectivity