Fully dynamic connectivity in O( n( n)^2) amortized expected time
From MaRDI portal
(Redirected from Publication:6566592)
Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
Cites work
- A data structure for dynamic trees
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Don't rush into a union, take time to find your roots
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Faster deterministic fully-dynamic graph connectivity
- Faster worst case deterministic dynamic connectivity
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Fully-dynamic minimum spanning forest with improved worst-case update time
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- Logarithmic Lower Bounds in the Cell-Probe Model
- Maintaining information in fully dynamic trees with top trees
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Near-optimal fully-dynamic graph connectivity
- Optimal lower bounds for distributed and streaming spanning forest computation
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms
- Sparsification—a technique for speeding up dynamic graph algorithms
Cited in
(4)
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 Q6566592)
