An EREW PRAM Algorithm for Updating Minimum Spanning Trees
An EREW PRAM Algorithm for Updating Minimum Spanning Trees
复制标题
一种更新最小生成树的 EREW PRAM 算法
DOI：
10.1142/s012962649900013x
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
P. Ferragina
中科院分区：
文献类型：
--
作者：
Sajal K. Das;P. Ferragina
提出了一种EREW PRAW模型的并行算法，该算法在单边插入和删除情况下保持无向图的最小生成树。对于一个有n个结点和m条边的图，每次更新需要O(Logn)时间和O(m2/3logn)工作。这是对工作复杂性的已知界限的实质性改进。我们的算法使用了MST的分区，类似于Frederickson[6]提出的顺序方法，并采用了一种新的数据结构来高效地并行管理边缘插入。
We propose a parallel algorithm for the EREW PRAW model that maintains a minimum spanning tree (MST) of an undirected graph under single edge insertions and deletions. For a graph of n nodes and m edges, each update requires O(log n) time and O(m2/3log n) work. This is a substantial improvement over the known bounds on the work complexity. Our algorithm uses a partition of the MST, similar to the sequential approach due to Frederickson [6], and also employs a novel data structure for efficiently managing edge insertions in parallel.