Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2016
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913231758426112 |
|---|---|
| author | Huang, Shang-En Huang, Dawei Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel |
| author_facet | Huang, Shang-En Huang, Dawei Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1609_05867 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time Huang, Shang-En Huang, Dawei Kopelowitz, Tsvi Pettie, Seth Thorup, Mikkel Data Structures and Algorithms 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). |
| title | Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1609.05867 |