TheoretiCS (May 2023)

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

DOI
https://doi.org/10.46298/theoretics.23.6
Journal volume & issue
Vol. Volume 2

Abstract

Read online

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

Keywords