Fully Dynamic Connectivity in O (log n (log log n ) 2 ) Amortized Expected Time
Fully Dynamic Connectivity in O (log n (log log n ) 2 ) Amortized Expected Time
复制标题
完全动态连接，时间复杂度为 O (log n (log log n ) 2 ) 摊销预期时间
DOI：
10.1137/1.9781611974782.32
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Huang, Shang-En;Huang, Dawei;Kopelowitz, Tsvi;Pettie, Seth
动态连通性是动态图算法中最基本的问题之一。我们提出了一个随机化的拉斯维加斯动态连接数据结构，其中具有1/2（log log log𝑛𝑛𝑂
Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with 𝑂 (log 𝑛 (log log 𝑛) 2) amortized expected update time and 𝑂 (log 𝑛/log log log 𝑛) worst case query time, which comes very close to the cell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup (2011).