一种有效的最小生成树并行算法

AN EFFICIENT PARALLEL ALGORITHM FOR THE MINIMUM SPANNING TREE PROBLEM

本文基于三维网孔处理机阵列，运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法．该算法需要Ｏ时间和Ｏ（ｐ）处理机．当时。

Based on three-dimensional processor mesh, a new and efficient algo rithm for computing minimum spanning tree of a weighted undirected graph is proposed with divide-and-conquer strategy and data-reduction technique. This algorithm requires O (n2/p+) time and O (p) processors. In particular, the time bound of this algorithm is O (logn) when