Fully Dynamic Connectivity in O(log n(loglog n)²) Amortized Expected Time
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:DHXH6LKZrecord.jsonopen to challenge →
classification
cs.DS
keywords
dynamicconnectivitytimeamortizedexpectedpatrascualgorithmsbounds
read the original abstract
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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.