# An O(log n) Time Common CRCW PRAM Algorithm for Minimum Spanning Tree

### Ramesh Subramonian

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-92-673

March 1992

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-673.pdf

We present a probabilistic algorithm for finding the minimum spanning tree of a graph with
*n* vertices and
*m* edges on a Common CRWC PRAM. It uses expected
*O*(log
*n* log*
*n*) time with (
*m* +
*n*) processors and expected
*O*(log
*n*) time with (
*m* +
*n*) log
*n* processors. This represents a significant improvement in terms of efficiency over the previous best results for solving this problem on a Common CRCW PRAM and compares favorably with the best result for the Priority CRCW PRAM, a more powerful model. The algorithm presents a novel application of recent results on recursive *-tree data structures. An important contribution of this paper is (i) a strategy to schedule the growth of components in algorithms based on repeated graph-contractions and (ii) an amortized analysis technique to account for the scheduling overhead.

BibTeX citation:

@techreport{Subramonian:CSD-92-673, Author = {Subramonian, Ramesh}, Title = {An O(log n) Time Common CRCW PRAM Algorithm for Minimum Spanning Tree}, Institution = {EECS Department, University of California, Berkeley}, Year = {1992}, Month = {Mar}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6133.html}, Number = {UCB/CSD-92-673}, Abstract = {We present a probabilistic algorithm for finding the minimum spanning tree of a graph with <i>n</i> vertices and <i>m</i> edges on a Common CRWC PRAM. It uses expected <i>O</i>(log <i>n</i> log* <i>n</i>) time with (<i>m</i> + <i>n</i>) processors and expected <i>O</i>(log <i>n</i>) time with (<i>m</i> + <i>n</i>) log <i>n</i> processors. This represents a significant improvement in terms of efficiency over the previous best results for solving this problem on a Common CRCW PRAM and compares favorably with the best result for the Priority CRCW PRAM, a more powerful model. The algorithm presents a novel application of recent results on recursive *-tree data structures. An important contribution of this paper is (i) a strategy to schedule the growth of components in algorithms based on repeated graph-contractions and (ii) an amortized analysis technique to account for the scheduling overhead.} }

EndNote citation:

%0 Report %A Subramonian, Ramesh %T An O(log n) Time Common CRCW PRAM Algorithm for Minimum Spanning Tree %I EECS Department, University of California, Berkeley %D 1992 %@ UCB/CSD-92-673 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6133.html %F Subramonian:CSD-92-673