Faster deterministic fully-dynamic graph connectivity

DOI10.1137/1.9781611973105.126MaRDI QIDQ5741835zbMATH OpenOpenAlexFDO

Authors Christian Wulff-Nilsen

Publication date 15 May 2019

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

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

Mathematics Subject Classification ID

Connectivity (05C40) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in $O(lo{g}^{2}n/loglogn)$ amortized time and connectivity queries in $O(logn/loglogn)$ worst-case time, where $n$ is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have $O(lo{g}^{2}n)$ amortized update time and $O(logn/loglogn)$ worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard $A{C}^0$ instructions.

Recommendations

• Faster worst case deterministic dynamic connectivity
• Near-optimal fully-dynamic graph connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• scientific article; zbMATH DE number 1775391
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Cited in

(27)

• Lower bounds for fully dynamic connectivity problems in graphs
• Speeding up dynamic transitive closure for bounded degree graphs
• Optimal decremental connectivity in planar graphs
• Constant-time dynamic weight approximation for minimum spanning forest
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Near-optimal fully-dynamic graph connectivity
• Connectivity oracles for graphs subject to vertex failures
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Faster worst case deterministic dynamic connectivity
• Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
• Deterministic Edge Connectivity in Near-Linear Time
• Decremental SPQR-trees for Planar Graphs
• Decremental strongly connected components and single-source reachability in near-linear time
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• Fully dynamic connectivity oracles under general vertex updates
• Dynamic graph connectivity in polylogarithmic worst case time
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Spatial mixing and the random‐cluster dynamics on lattices
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
• Dynamic connectivity in disk graphs
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Fully dynamic strongly connected components in planar digraphs
• Near-linear time samplers for matroid independent sets with applications
• Deterministic fault-tolerant connectivity labeling scheme
• A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks

This page was built for publication: Faster deterministic fully-dynamic graph connectivity

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