%0 Journal Article
%T 多处理器上求最小生成树的并行算法
%J 北京理工大学学报
%D 1999
%X 目的给出无向图Ｇ（Ｖ，Ｅ），｜Ｖ｜＝ｎ的最小生成树在单指令流多数据流（ＳＩＭＤ）机器、Ｉｎｃｏｍｐｌｅｔｅ－ｈｙｐｅｒｃｕｂｅ上的并行算法．方法利用有ｐ个处理器的不完全超立方网络，求加权无向连通图Ｇ（Ｖ，Ｅ），｜Ｖ｜＝ｎ的最小生成树．结果与结论若处理器的个数为ｐ，则其时间复杂性为ｔ（ｎ）＝Ｏ（ｎ２／ｐ·（ｌｂｐ）），成本Ｃ（ｎ）＝Ｏ（ｎ２（ｌｂｐ）），它几乎是最优的．
%K 并行算法
%K 最小生成树
%K SIMD机器
%K 多处理器
%U http://journal.bit.edu.cn/zr/ch/reader/view_abstract.aspx?file_no=19990389&flag=1