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

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

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.

I: TheoretiCS, Bind 2, 6, 2023, s. 1-56.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Huang, S, Huang, D, Kopelowitz, T, Pettie, S & Thorup, M 2023, 'Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time', TheoretiCS, bind 2, 6, s. 1-56. https://doi.org/10.46298/theoretics.23.6

APA

Huang, S., Huang, D., Kopelowitz, T., Pettie, S., & Thorup, M. (2023). Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time. TheoretiCS, 2, 1-56. [6]. https://doi.org/10.46298/theoretics.23.6

Vancouver

Huang S, Huang D, Kopelowitz T, Pettie S, Thorup M. Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time. TheoretiCS. 2023;2:1-56. 6. https://doi.org/10.46298/theoretics.23.6

Author

Huang, Shang-en ; Huang, Dawei ; Kopelowitz, Tsvi ; Pettie, Seth ; Thorup, Mikkel. / Fully Dynamic Connectivity in O (log n((log log n)2 Amortized Expected Time. I: TheoretiCS. 2023 ; Bind 2. s. 1-56.

Bibtex

@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",

}

RIS

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

VL - 2

SP - 1

EP - 56

JO - TheoretiCS

JF - TheoretiCS

SN - 2751-4838

M1 - 6

ER -

ID: 384257394