摘要
已知一个无向图G(V,E),|V|=n.本文在SIMD机器-Hype-rcube上提出了计算图的连通分支和最小生成树的两个最优算法.若Hypercu-be由P个处理器组成,则上述两个算法的时间复杂性都是O(n^2/p),1≤p且PlogP≤n.
Given an undirected graph G(V, E), |V|=n, two optimal algorithms for computing connected-components and a minimum spanning tree are proposed on SIMD machine-Hypercube. If the Hypercube multiprocessor consists of p processors, our algorithms require O(n2/p) time, 1≤p and p logp≤n.
出处
《计算机学报》
EI
CSCD
北大核心
1991年第9期641-650,共10页
Chinese Journal of Computers
基金
"863"计划资助
关键词
多处理器
图
最优算法
互连网络
Parallel algorithms, minimum spanning tree, connected component, graph theory, SIMD machine, interconnection networks.
