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

theoretics:9645 - TheoretiCS, May 2, 2023, Volume 2 - https://doi.org/10.46298/theoretics.23.6
Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected TimeArticle

Authors: Shang-En Huang ; Dawei Huang ; Tsvi Kopelowitz ; Seth Pettie ; Mikkel Thorup ORCID

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

    https://doi.org/10.46298/theoretics.23.6
    Source: arXiv.org:1609.05867
    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
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • AF: Medium: Collaborative Research: Hardness in Polynomial Time; Funder: National Science Foundation; Code: 1514383
    • AF:Small:Data Structures for Dynamic Networks; Funder: National Science Foundation; Code: 1217338
    • TWC: Small: Collaborative: Cost-Competitve Analysis - A New Tool for Designing Secure Systems; Funder: National Science Foundation; Code: 1318294

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    1 Document citing this article

    Share and export

    Consultation statistics

    This page has been seen 631 times.
    This article's PDF has been downloaded 626 times.