A Technique to Speed Up Parallel Fully Dynamic Algorithms for MST |
| |
| Authors: | Ferragina P. |
| |
| Affiliation: | 1. Departamento de Engenharia de Produção, Universidade Federal Fluminense, Rua Passo da Pátria, 156 São Domingos, Bloco E – 4o andar, Niterói – RJ, 24210-240, Brazil;2. Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, Rua Marquês de São Vicente, 225 Gávea, Rio de Janeiro – RJ, 22451-900, Brazil;3. Departamento de Sistemas de Computação Centro de Informática, Universidade Federal da Paraíba, Rua dos Escoteiros, Mangabeira, João Pessoa – PB, 58058-600, Brazil |
| |
| Abstract: | 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(n2/3 log(m/n)) work, where n and m are respectively the number of nodes and edges of the given graph. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
