稀疏图上有效的MST多边更新并行算法

An Efficient Parallel Algorithm for Multiple Edge Updates of MST on Sparse Graph

ＭＳＴ（最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ之略）多边更新（ｕｐｄａｔｉｎｇ）问题定义如下：给定一个赋权图Ｇ（Ｖ，Ｅ）和Ｇ的一棵最小生成树Ｔ（Ｖ，ＥＴ），其中｜Ｖ｜＝ｎ，ＥＴ是树边集合，（１）给Ｇ添加Ｋ条新边，或者（２）在图Ｇ上改变Ｋ条边的权后重新为Ｇ寻找一棵最小生成树，１≤Ｋ＜ｎ．本文基于ＳＩＭＤＣＲＥＷＰＲＡＭ共享存贮模型，运用“进－退”策略，并把这一特殊手段与已有的平行算法组合起来，为一类稀疏图（｜Ｅ—ＥＴ｜＝Ｏ（Ｋ））找到了一种有效的ＭＳＴ多边更新算法．该算法需要Ｏ（ｌｏｇｎｌｏｇＫ）时间和Ｏ（ｍａｘ｛ｎ，ｕＫ／ｌｏｇｎｌｏｇＫ｝）处理机．

The multiple edge updating problem for a minimum spanning tree (MST) isdefined as follows: Given a weighted graph G (V, E) and its MST T (V, ET),where |V|=n, ET is the set of tree edges, recompute a new minimum spanningtree after (1) adding K new edges, or (2) changing the weights of K edges onthe graph G, where 1≤K<n. Based on a SIMD CREW PRAM model, an efficient algorithm for multiple edge updates of MST on a sparse graph (|E-ET|= O(K)) is found with 'advance-and-retreat' strategy and combining this specialway with some existent parallel algorithms. The algorithm requires O(log n logK) time and O(max{n,nK/log n log K} ) processors.