A parallel algorithm for multiple edge updates of minimum spanning trees

The authors present a parallel algorithm for the multiple edge update problem on a minimum spanning tree. This problem is defined as follows: given a minimum spanning tree T(V,E _T) of an undirected graph G(V,E), where |V|=n and E_T is the set of tree edges, recompute a new minimum spanning tree when (1) adding K new edges, (2) changing the weights of existent K edges, or (3) deleting a vertex of degree K in the tree, where 1⩽ K<n. Their algorithm requires O(logK logn) time and O(n²/logn logK) processors on a SIMD CREW PRAM model. If the weights of the current tree edges are not allowed to increase, then their algorithm runs in the same time bound, but only using O(max{n,nK/lognlogK}) processors. Their algorithm is optimal for dense graphs, if no intermediate results are available from computing the original MST