Title: Deterministic Worst Case Dynamic Connectivity: Simpler and Faster.
Abstract: 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.
Publication Year: 2015
Publication Date: 2015-07-21
Language: en
Type: preprint
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot