Faster Fully-Dynamic Minimum Spanning Forest
From MaRDI portal
Publication:3452837
DOI10.1007/978-3-662-48350-3_62zbMath1467.68141arXiv1407.6832OpenAlexW2133521834MaRDI QIDQ3452837
Jacob Holm, Christian Wulff-Nilsen, Eva Rotenberg
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.6832
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (7)
On Locality-Sensitive Orderings and Their Applications ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ Dynamic geometric data structures via shallow cuttings ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest
Cites Work
- Sorting in linear time?
- Maintaining information in fully dynamic trees with top trees
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Near-optimal fully-dynamic graph connectivity
- Lower bounds for dynamic connectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms
- Sparsification—a technique for speeding up dynamic graph algorithms
- Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
This page was built for publication: Faster Fully-Dynamic Minimum Spanning Forest
