Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time

Shang-en Huang; Dawei Huang; Tsvi Kopelowitz; Seth Pettie; Mikkel Thorup

doi:10.46298/theoretics.23.6

Fully Dynamic Connectivity in O (log n((log log n)² Amortized Expected Time

Shang-en Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup

Algorithms and Complexity

Research output: Contribution to journal › Journal article › Research › peer-review

10 Downloads (Pure)

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(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).

Original language	English
Article number	6
Journal	TheoretiCS
Volume	2
Pages (from-to)	1-56
DOIs	https://doi.org/10.46298/theoretics.23.6
Publication status	Published - 2023

Access to Document

10.46298/theoretics.23.6Licence: CC BY

FulltextFinal published version, 745 KBLicence: CC BY

Cite this

@article{f3964db08ca54eb49b66027af7e3b187,

title = "Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time",

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(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).",

author = "Shang-en Huang and Dawei Huang and Tsvi Kopelowitz and Seth Pettie and Mikkel Thorup",

year = "2023",

doi = "10.46298/theoretics.23.6",

language = "English",

volume = "2",

pages = "1--56",

journal = "TheoretiCS",

issn = "2751-4838",

publisher = "TheoretiCS Foundation",

}

TY - JOUR

T1 - Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time

AU - Huang, Shang-en

AU - Huang, Dawei

AU - Kopelowitz, Tsvi

AU - Pettie, Seth

AU - Thorup, Mikkel

PY - 2023

Y1 - 2023

N2 - 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).

AB - 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).

U2 - 10.46298/theoretics.23.6

DO - 10.46298/theoretics.23.6

M3 - Journal article

SN - 2751-4838

VL - 2

SP - 1

EP - 56

JO - TheoretiCS

JF - TheoretiCS

M1 - 6

ER -