逼近最优的更新最小生成树的并行算法

TOWARDS OPTIMAL PARALLEL ALGORITHM FOR UPDATING MINIMUM SPANNING TREES

给定连通无向赋值图G=(V,E),|V|=n,|E|=m,当G的某边的赋值改变时,必引起其最小生成树的改变。本文给出了一个快速有效地求新的最小生成树的并行算法,时间为O(log m),处理器个数为O(m^(1/2)),计算模型为EREW-PRAM。预处理也仅需O(log^2m)时间O(m)个处理器,与求初始最小生成树的耗费一样。我们的算法的并行时间与处理四个数的乘积为O(m^(1/2) log m)(此问题已知最快的串行算法时间为O(m^(1/2)))。

Given an undirected connected weighted graph G = (V,E), where |V| = n, | E | = m, the MST T of G might be changed when the cost of some edge of G changes. A parallel algorithm to find a new MST of G is presented in EREW-PRAM model with O(logm) time and O(m) processors. The product of paralleltime and the number of processors is near to the time O(m) of the known best sequential algorithm. And the cost of preliminary processing, where t = O(log2m) and p = O(m), is the same as the cost of finding initial MST of G.