Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized
Expected TimeArticleAuthors: Shang-En Huang ; Dawei Huang ; Tsvi Kopelowitz ; Seth Pettie ; Mikkel Thorup

NULL##NULL##NULL##NULL##0000-0001-5237-1709
Shang-En Huang;Dawei Huang;Tsvi Kopelowitz;Seth Pettie;Mikkel Thorup
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).
Volume: Volume 2
Published on: May 2, 2023
Accepted on: March 15, 2023
Submitted on: June 3, 2022
Keywords: Computer Science - Data Structures and Algorithms
Funding:
Source : OpenAIRE Graph- AF: Medium: Collaborative Research: Hardness in Polynomial Time; Funder: National Science Foundation; Code: 1514383
- TWC: Small: Collaborative: Cost-Competitve Analysis - A New Tool for Designing Secure Systems; Funder: National Science Foundation; Code: 1318294
- AF:Small:Data Structures for Dynamic Networks; Funder: National Science Foundation; Code: 1217338