Faster worst case deterministic dynamic connectivity

DOI10.4230/LIPICS.ESA.2016.53MaRDI QIDQ4606324zbMATH OpenOpenAlexFDO

Authors Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup

Publication date 2 March 2018

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

zbMATH Keywords

spanning treedynamic graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Connectivity (05C40)

Abstract: We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time $Oleft(sqrtfracn(loglogn{)}^{2}lognight)$ and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (STOC 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM 1997), which had update time $O(sqrtn)$. All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

Recommendations

• Faster deterministic fully-dynamic graph connectivity
• Dynamic graph connectivity in polylogarithmic worst case time
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Near-optimal fully-dynamic graph connectivity
• scientific article; zbMATH DE number 1263228

Cited in

(17)

• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Faster deterministic fully-dynamic graph connectivity
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Good r-divisions imply optimal amortized decremental biconnectivity
• Dynamic connectivity in digital images
• New data structures for subgraph connectivity
• Dynamic Connectivity for Axis-Parallel Rectangles
• Decremental SPQR-trees for Planar Graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Faster randomized worst-case update time for dynamic subgraph connectivity
• Fully dynamic connectivity oracles under general vertex updates
• Don't rush into a union, take time to find your roots
• Approximating dynamic weighted vertex cover with soft capacities
• Optimal decremental connectivity in planar graphs
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Dynamic graph connectivity in polylogarithmic worst case time
• Connectivity oracles for graphs subject to vertex failures

This page was built for publication: Faster worst case deterministic dynamic connectivity

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