| 最小生成树问题在RMESH上的常数时间算法 |
| |
| 引用本文： | 陈鹏,霍金健,张立昂.最小生成树问题在RMESH上的常数时间算法[J].北京大学学报(自然科学版),2006,42(1):83-88. |
| |
| 作者姓名： | 陈鹏 霍金健 张立昂 |
| |
| 作者单位： | 北京大学信息科学技术学院，北京，100871 |
| |
| 摘 要： | 提出了在n2×mn2的RMESH模型上常数时间的最小生成树算法，并根据PRAM模拟RMESH的结论，得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。
|
| 关 键 词： | RMESH 并行算法 最小生成树 |
| 收稿时间： | 2004-10-11 |
| 修稿时间： | 2004-10-112005-03-01 |
A Constant Time Algorithm for MST on RMESH |
| |
| CHEN Peng,HUO Jinjian,ZHANG Li'ang.A Constant Time Algorithm for MST on RMESH[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2006,42(1):83-88. |
| |
| Authors: | CHEN Peng HUO Jinjian ZHANG Li'ang |
| |
| Institution: | School of Electronics Engineering and Computer Science, Peking University, Beijing, 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. |
| |
| Keywords: | RMESH |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《北京大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《北京大学学报(自然科学版)》下载免费的PDF全文 |
