%0 Journal Article
%T An Efficient Parallel Minimum Spanning Tree Algorithm on Message Passing Parallel Machine<br>在消息传递并行机上的高效的最小生成树算法
%A WANG Guang-rong
%A GU Nai-jie
%A <br>王光荣
%A 顾乃杰
%J 软件学报
%D 2000
%I 
%X An efficient parallel minimum spanning tree is proposed based on the classical Borüvka's algorithm on message passing parallel machine. Three methods were used to improve its efficiency, including two-phase union and packaged contraction for reducing communication costs, and the balanced data distribution for computation balance in each processor. The computation and communication costs of the algorithm are O(n2/p) and O((tsp+twn)n/p). On Dawning-1000 parallel machine, it gets a speedup of 12 on 16 processors with a sparse graph of 10 000 vertices.
%K MPP (message passing parallel)
%K MST (minimum spanning tree)
%K parallel algorithm
%K communication
%K disjoint set<br>MPP
%K (message
%K passing
%K parallel)
%K MST
%K (minimum
%K spanning
%K tree)，并行算法，通信，非关联图.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=F804C4A7AD2506D1&yid=9806D0D4EAA9BED3&vid=708DD6B15D2464E8&iid=DF92D298D3FF1E6E&sid=BF6EDE6C10074464&eid=9124D83E61CF1CD0&journal_id=1000-9825&journal_name=软件学报&referenced_num=5&reference_num=13