Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
TheoretiCS · 2023
DOI: 10.46298/theoretics.23.6 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von Shang-En Huang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).
Abstract (Originalsprache)
Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with $O(\log n(\log\log n)^2)$ amortized expected update time and $O(\log n/\log\log\log n)$ worst case query time, which comes very close to the cell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup (2011).
Zitieren
APA
Huang, S., Huang, D., Kopelowitz, T., Pettie, S., & Thorup, M. (2023). Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time. TheoretiCS. https://doi.org/10.46298/theoretics.23.6
Vancouver
Huang S, Huang D, Kopelowitz T, Pettie S, Thorup M. Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time. TheoretiCS. 2023. doi:10.46298/theoretics.23.6
BibTeX
@article{Huang2023,
author = {Huang, Shang-En and Huang, Dawei and Kopelowitz, Tsvi and Pettie, Seth and Thorup, Mikkel},
title = {Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time},
journal = {TheoretiCS},
year = {2023},
doi = {10.46298/theoretics.23.6}
}
EUVIMED