Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

A Constant Time Algorithm for MST on RMESH

CHEN Peng, HUO Jinjian, ZHANG Li'ang   

  1. School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871
  • Received:2004-10-11 Online:2006-01-20 Published:2006-01-20

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

陈鹏,霍金健,张立昂   

  1. 北京大学信息科学技术学院,北京,100871

Abstract: A constant time algorithm for minimum spanning tree problem on a n2×mn2 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

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

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

CLC Number: