网孔处理机阵列上最小生成树算法

A PARALLEL ALGORITHM FOR THE MINIMUM SPANNING TREE PROBLEM BASED ON MESH ARRAY

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n^2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n^2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.

Based on mesh processor array, a new algorithm for computing minimum spanning tree of a weighted undirected graph is proposed with divide-and-conquer strategy and data-reduce technique. This algorithm requires O(n2/p) time and O(p) processors (1≤p≤n). In particular, the algorithm only requires O(n) time and O(n) processors when p = n. Since the best algorithm for this problem, based on the same computing model, requires O(n) time and O(n2) processors, the proposed algorithm decreases a factor of O(n) in the number of processors.