A parallel algorithm for computing minimum spanning trees

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V;E) of n = jV j vertices andm = jEj edges on an EREW PRAM in O(log3=2n) time using n+m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.