| 一种有效的最小生成树并行算法 |
| |
| 引用本文： | 郁松年. 一种有效的最小生成树并行算法[J]. 计算机学报, 1994, 17(6): 469-472 |
| |
| 作者姓名： | 郁松年 |
| |
| 作者单位： | 上海工业大学计算机工程系 |
| |
| 摘 要： | 本文基于三维网孔处理机阵列，运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法。
|
| 关 键 词： | 并行算法 最小生成树 数据结构 |
AN EFFICIENT PARALLEL ALGORITHM FOR THE MINIMUM SPANNING TREE PROBLEM |
| |
| Yu Songnian. AN EFFICIENT PARALLEL ALGORITHM FOR THE MINIMUM SPANNING TREE PROBLEM[J]. Chinese Journal of Computers, 1994, 17(6): 469-472 |
| |
| Authors: | Yu Songnian |
| |
| Abstract: | Based on three-dimensional processor mesh, a new and efficient algo rithm for computing minimum spanning tree of a weighted undirected graph is proposed with divide-and-conquer strategy and data-reduction technique. This algorithm requires O (n2/p ) time and O (p) processors. In particular, the time bound of this algorithm is O (logn) when |
| |
| Keywords: | Parallel algorithm minimum spanning tree three-dimensional mesh SIMD model |
| 本文献已被 CNKI 维普 等数据库收录！ |
