An Efficient Asynchronized Algorithm for the MST Problem

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.