A TECHNIQUE TO SPEED-UP PARALLEL FULLY DYNAMIC ALGORITHMS FOR MST

We provide a new EREW PRAM algorithm to maintain the minimum spanning tree (MST) of an undirected weighted graph. Our approach combines the sparsification data structure with a novel parallel technique which ef ficiently treats single edge deletions. The proposed parallel algorith m requires O(log n) time and O(n(2/3) log(m/n)) work, where n and m ar e respectively the number of nodes and edges of the given graph. (C) 1 995 Academic Press, Inc.