EUVIMEDEUVIMED entdecken
Crossref

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time

Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →