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

北京大学学报（自然科学版）

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

陈鹏,霍金健,张立昂

北京大学信息科学技术学院，北京，100871

收稿日期:2004-10-11 出版日期:2006-01-20 发布日期:2006-01-20

A Constant Time Algorithm for MST on RMESH

CHEN Peng, HUO Jinjian, ZHANG Li'ang

School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871

Received:2004-10-11 Online:2006-01-20 Published:2006-01-20

摘要/Abstract

摘要： 提出了在n²×mn²的RMESH模型上常数时间的最小生成树算法，并根据PRAM模拟RMESH的结论，得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。

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

Abstract: A constant time algorithm for minimum spanning tree problem on a n²×mn² 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.

Key words: parallel algorithm, minimum spanning tree

中图分类号:

TP301.6

陈鹏,霍金健,张立昂. 最小生成树问题在RMESH上的常数时间算法[J]. 北京大学学报（自然科学版）.

CHEN Peng,HUO Jinjian,ZHANG Li'ang. A Constant Time Algorithm for MST on RMESH[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

[1]	盛向治,单宝松. 基于GPGPU的多目的混音算法的研究与实现[J]. 北京大学学报（自然科学版）, 2008, 44(1): 49-54.
[2]	程红兵,马猛,焦秉立. 一种用于CP-CDMA系统的正交频率分组码：梳状频谱码[J]. 北京大学学报（自然科学版）, 2005, 41(3): 476-483.
[3]	陈鹏,张立昂. PRAM模型模拟RMESH模型的2种方案[J]. 北京大学学报（自然科学版）, 2005, 41(3): 465-475.