A Parallel Algorithm for Computing Minimum Spanning Trees

✍ Scribed by D.B. Johnson; P. Metaxas

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 840 KB
• Volume: 19
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1043

✦ Synopsis

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph (G=(V, E)) of (n=|V|) vertices and (m=|E|) edges on an EREW PRAM in (O\left(\log ^{3 / 2} n\right)) 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. 1995 Academic Press, Inc.