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

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

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