Fully dynamic connectivity in O(log n(log log n)2) amortized expected time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie · arXiv (Cornell University) · 2017
Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)2) amortized expected update time and O(log n/log log log n) query time, which comes within an O((log log n)2) factor of a lower bound due to Pǎtrascu and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details.