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

Shang-En Huang, Dawei Huang, Tsvi Kopelowitz +2

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\…