Fully dynamic connectivity in O( n( n)^2) amortized expected time

DOI10.1137/1.9781611974782.32MaRDI QIDQ4575769zbMATH OpenOpenAlexFDO

Authors Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05867

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05) Connectivity (05C40)

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

Recommendations

• Near-optimal fully-dynamic graph connectivity
• Faster deterministic fully-dynamic graph connectivity
• scientific article; zbMATH DE number 1263228
• Faster worst case deterministic dynamic connectivity
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Cited in

(19)

• Incomplete directed perfect phylogeny in linear time
• Near-optimal fully-dynamic graph connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Dynamic connectivity in disk graphs
• Faster deterministic fully-dynamic graph connectivity
• An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Faster worst case deterministic dynamic connectivity
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Constant-time dynamic weight approximation for minimum spanning forest
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Optimal offline dynamic 2, 3-edge/vertex connectivity
• Don't rush into a union, take time to find your roots
• Decremental strongly connected components and single-source reachability in near-linear time
• Lower bounds for dynamic connectivity
• Dynamic graph connectivity in polylogarithmic worst case time
• Connectivity oracles for graphs subject to vertex failures

This page was built for publication: Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575769)