Faster Fully-Dynamic Minimum Spanning Forest
classification
💻 cs.DS
keywords
amortizedforestfully-dynamicminimumspanningassumebounddata
read the original abstract
We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in $O(\log^4n/\log\log n)$ amortized time per operation, improving the $O(\log^4n)$ amortized bound of Holm et al. (STOC'98, JACM'01). We assume the Word-RAM model with standard instructions.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.