Vi presenterar en deterministisk dynamisk konnektivitet datastruktur för oriktade grafer med värsta fall uppdateringstid O n(log log n) 2 log n och konstant frågetid. Detta förbättrar den tidigare bästa deterministiska värsta fallalgoritmen för Frederickson (STOC, 1983) och Eppstein Galil, Italiano och Nissenzweig (J. ACM, 1997), som hade uppdateringstid O ( ε n). Alla andra algoritmer för dynamisk konnektivitet är antingen randomiserade (Monte Carlo) eller har endast amorterade prestandagarantier.
Först nyligen förbättrades detta något av Kejlberg-Rasmussen et al. REF, som kunde få ett värsta fall uppdateringstid för O n (logglogg n) 2 log n.
Faster Worst Case Deterministic Dynamic Connectivity