Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
From MaRDI portal
Publication:4575769
DOI10.1137/1.9781611974782.32zbMath1410.68299arXiv1609.05867OpenAlexW2522910400MaRDI QIDQ4575769
Seth Pettie, Tsvi Kopelowitz, Shang-En Huang, Dawei Huang
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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)
Related Items
Incomplete directed perfect phylogeny in linear time ⋮ Dynamic connectivity in disk graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ 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 ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time