Title :
An EREW PRAM fully-dynamic algorithm for MST
Author :
Ferragina, Paolo
Author_Institution :
Dipartimento di Inf., Pisa Univ., Italy
Abstract :
We provide an EREW PRAM fully-dynamic algorithm to maintain the minimum spanning tree (MST) of an undirected weighted graph under single edge insertions and deletions. Our approach combines the sparsification data structure with a novel parallel technique which efficiently treats edge deletions. The proposed parallel algorithm requires O(log n) time and O(n2/3 log m/n) work, where n and m are respectively the number of nodes and edges of the given graph
Keywords :
computational complexity; parallel algorithms; tree data structures; trees (mathematics); EREW PRAM fully-dynamic algorithm; minimum spanning tree; nodes; parallel algorithm; single edge deletions; single edge insertions; sparsification data structure; time; undirected weighted graph; work; Algorithm design and analysis; Continuous wavelet transforms; Data structures; Parallel algorithms; Phase change random access memory; Read-write memory; Tree graphs;
Conference_Titel :
Parallel Processing Symposium, 1995. Proceedings., 9th International
Conference_Location :
Santa Barbara, CA
Print_ISBN :
0-8186-7074-6
DOI :
10.1109/IPPS.1995.395919
