最小生成树的高效异步并行算法  

An Efficient Asynchronized Algorithm for the MST Problem

作　　者：马军[1] 马绍汉[1] 

机构地区：[1]山东大学计算机系

出　　处：《计算机研究与发展》1994年第2期1-4,共4页Journal of Computer Research and Development

基　　金：山东省自然科学基金

摘　　要：在ＭＩＭＤ－ＳＭ并行计算模型上，本文给出了时间复杂性为Ｏ（ｎ（ｎ／Ｐ＋ｌｏｇｐ））的是小生成树的异步并行算法，其中ｎ，Ｐ（１≤ｐ≤ｎ）分别表示图的顶点数和处理机的个数。In this paper, an O(n(n/p+logp))asynchronized parallel algorithm to find the minimum spanning tree in an undirected graph on the MIMD-SM parallel model is given, where n is the num her of venices in graph and p (1≤p≤n) is the number of processors used. The Ada language is used to implement the algorithm.

关 键 词：数据结构 最小生成树 并行算法 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]