Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time
Research output: Contribution to journal › Journal article › Research › peer-review
Documents
- Fulltext
Final published version, 745 KB, PDF document
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(logn(loglogn)2)
amortized expected update time and O(logn/logloglogn)
worst case query time, which comes very close to the cell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup (2011).
amortized expected update time and O(logn/logloglogn)
worst case query time, which comes very close to the cell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup (2011).
| Original language | English |
|---|---|
| Article number | 6 |
| Journal | TheoretiCS |
| Volume | 2 |
| Pages (from-to) | 1-56 |
| DOIs | |
| Publication status | Published - 2023 |
ID: 384257394