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

dynamic graphspanning tree

Mathematics Subject Classification ID

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

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)

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

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)