Faster Fully-Dynamic Minimum Spanning Forest

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

Mathematics Subject Classification ID

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