Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.
Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup · arXiv (Cornell University) · 2015
We present a deterministic dynamic connectivity data structure for undirected graphs with worst-case update time $O(\sqrt{n}/w^{1/4})$ and constant query time, where $w = \Omega(\log n)$ is the word size. This bound improves on the previous best deterministic worst-case algorithm of Frederickson (STOC, 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), having update time $O(\sqrt{n})$. All known faster dynamic connectivity algorithms are either randomized, or have amortized updates, or both.