最小生成树问题在RMESH上的常数时间算法  

A Constant Time Algorithm for MST on RMESH

作　　者：陈鹏[1] 霍金健[1] 张立昂[1] 

机构地区：[1]北京大学信息科学技术学院,北京100871

出　　处：《北京大学学报（自然科学版）》2006年第1期83-88,共6页Acta Scientiarum Naturalium Universitatis Pekinensis

摘　　要：提出了在n2×mn2的RMESH模型上常数时间的最小生成树算法,并根据PRAM模拟RMESH的结论,得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。A constant time algorithm for minimum spanning tree problem on a n^2×mn^2 RMESH is introduced. Based on the conclusion of simulating RMESH by PRAM, there is an O （logn） algorithm for MST on PRAM. The time complexity of these algorithms is the best so far.

关 键 词：RMESH 并行算法 最小生成树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]