Faster Fully-Dynamic Minimum Spanning Forest

DOI10.1007/978-3-662-48350-3_62MaRDI QIDQ3452837zbMATH OpenOpenAlexFDO

Authors Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen

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

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in $O(lo{g}^{4}n/loglogn)$ amortized time per operation, improving the $O(lo{g}^{4}n)$ amortized bound of Holm et al. (STOC'98, JACM'01). We assume the Word-RAM model with standard instructions.

Recommendations

• Fully-dynamic minimum spanning forest with improved worst-case update time
• Constant-time dynamic weight approximation for minimum spanning forest
• Maintaining minimum spanning forests in dynamic graphs
• Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs
• Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
• scientific article; zbMATH DE number 3980506
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A fast distributed approximation algorithm for minimum spanning trees
• Fast approximation algorithms for computing constrained minimum spanning trees
• A faster distributed protocol for constructing a minimum spanning tree

Cites work

• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Lower bounds for dynamic connectivity
• Maintaining information in fully dynamic trees with top trees
• Near-optimal fully-dynamic graph connectivity
• 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
• Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Sorting in linear time?
• Sparsification—a technique for speeding up dynamic graph algorithms

Cited in

(13)

• Constant-time dynamic weight approximation for minimum spanning forest
• Dynamic geometric data structures via shallow cuttings
• Maintaining minimum spanning forests in dynamic graphs
• On locality-sensitive orderings and their applications
• Offline Algorithms for Dynamic Minimum Spanning Tree Problems
• Maintaining centdians in a fully dynamic forest with top trees
• Fully-dynamic minimum spanning forest with improved worst-case update time
• Decremental SPQR-trees for Planar Graphs
• scientific article; zbMATH DE number 7559224 (Why is no real title available?)
• On Locality-Sensitive Orderings and Their Applications
• Optimal lower bounds for distributed and streaming spanning forest computation
• Deterministic maximum flows in simple graphs
• Upper and lower bounds for fully retroactive graph problems

This page was built for publication: Faster Fully-Dynamic Minimum Spanning Forest

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