多处理器上求最小生成树的并行算法

摘要：

目的给出无向图G(V,E),|V|=n的最小生成树在单指令流多数据流(SIMD)机器、Incomplete-hypercube上的并行算法.方法利用有p个处理器的不完全超立方网络,求加权无向连通图G(V,E),|V|=n的最小生成树.结果与结论若处理器的个数为p,则其时间复杂性为t(n)=O(n2/p.(lb p)),成本C(n)=O(n2(lb p)),它几乎是最优的.

关键词：并行算法、最小生成树、SIMD机器

所属期刊栏目：19

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页码：329-333