在线性处理机阵列上求MCST的并行算法

A PARALLEL ALGORITHM FOR COMPUTING MCST ON THE LINEAR PROCESSOR ARRAY

本文给出一种在P个处理机线性阵列上求MCST(最小代价生成树)的并行算法,记为OLA-MCST.证明了在整个1≤P≤n范围内其时间复杂性均为O(n^2/P);特别地,当P=n时,为O(n).这是在本模型下使用n个处理机时的最优性能.

In this paper, a parallel algorithm for computing MCST (Minimum Cost Spanning Tree) on a fixed-size linear array of processors is presented. F or a graph of n vertices, the algorithm requires O(n2/p) time for all 1 ≤ p≤n. In particular, when p=n, the algorithm requires O(n) time which is optimal on the model.