Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
Preprint
Abstract
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with $n$ vertices and $m$ edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(\sqrt n)$ processors and $O(\log n)$ worst-case update time, for a total of $O(\sqrt n \log n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(\log n)$ worst-case update time and $O(n^{2/3} \log{\frac{m}{n}})$ work.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Fully-Dynamic Min-Cut*Combinatorica, 2007
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985