Constant-time dynamic weight approximation for minimum spanning forest
From MaRDI portal
Publication:2051831
DOI10.1016/j.ic.2021.104805OpenAlexW3202568496MaRDI QIDQ2051831
Publication date: 25 November 2021
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.00977
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for fully dynamic connectivity problems in graphs
- Dynamic graph stream algorithms in \(o(n)\) space
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Estimating the number of connected components in sublinear time
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Fully dynamic randomized algorithms for graph spanners
- Near-optimal fully-dynamic graph connectivity
- Faster Fully-Dynamic Minimum Spanning Forest
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Sparsification—a technique for speeding up dynamic graph algorithms
- Maintaining minimum spanning trees in dynamic graphs
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Logarithmic Lower Bounds in the Cell-Probe Model
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
