Fully-dynamic minimum spanning forest with improved worst-case update time
From MaRDI portal
Abstract: We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n^{1/2 - c}) expected worst-case time for some constant c > 0 and this worst-case bound holds with probability at least 1 - n^{-d} where d is a constant that can be made arbitrarily large. This is the first data structure achieving an improvement over the O(n^{1/2}) deterministic worst-case update time of Eppstein et al., a bound that has been standing for nearly 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Theta(n^{1/2}). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Theta(n^{1/2}) w.h.p.; this data structure has O(1) worst-case query time.
Recommendations
- Faster Fully-Dynamic Minimum Spanning Forest
- Maintaining minimum spanning forests in dynamic graphs
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Constant-time dynamic weight approximation for minimum spanning forest
- Maintaining minimum spanning trees in dynamic graphs
Cited in
(16)- Constructing Light Spanners Deterministically in Near-Linear Time
- Simple dynamic spanners with near-optimal recourse against an adaptive adversary
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Decremental SPQR-trees for Planar Graphs
- Maintaining minimum spanning forests in dynamic graphs
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Faster connectivity in low-rank hypergraphs via expander decomposition
- Constant-time dynamic weight approximation for minimum spanning forest
- Practical expander decomposition
- Faster Fully-Dynamic Minimum Spanning Forest
- Fast algorithms via dynamic-oracle matroids
- Finding a small vertex cut on distributed networks
- Improved dynamic graph coloring
- Negative-weight single-source shortest paths in near-linear time
- Constructing light spanners deterministically in near-linear time
This page was built for publication: Fully-dynamic minimum spanning forest with improved worst-case update time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978053)
