We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O n(log log n) 2 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.
Only recently this was slightly improved by Kejlberg-Rasmussen et al. REF , who were able to obtain a worst case update time of O n(log log n) 2 log n .
Faster Worst Case Deterministic Dynamic Connectivity