Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
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 t...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
TheoretiCS Foundation e.V.
2023-05-01
|
| Series: | TheoretiCS |
| Subjects: | |
| Online Access: | https://theoretics.episciences.org/9645/pdf |