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