A Technique to Speed Up Parallel Fully Dynamic Algorithms for MST

✍ Scribed by P. Ferragina

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 826 KB
• Volume: 31
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1995.1157

✦ Synopsis

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 efficiently treats single edge deletions. The proposed parallel algorithm requires (O(\log n)) time and (O\left(n^{2 / 3} \log (m / n)\right)) work, where (n) and (m) are respectively the number of nodes and edges of the given graph. 1995 Academic Press, lnc.