2026-10-01T16:36:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6395 2026-09-30T03:30:54Z ddc:004 open_access

Faster Worst Case Deterministic Dynamic Connectivity Kejlberg-Rasmussen, Casper Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel dynamic graph spanning tree We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(sqrt{(n(log(log(n)))^2)/log(n)}) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(sqrt{n}). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Casper Kejlberg-Rasmussen and Tsvi Kopelowitz and Seth Pettie and Mikkel Thorup 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.53 urn:nbn:de:0030-drops-63953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.53 eng https://creativecommons.org/licenses/by/3.0/legalcode