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

, 1992

http://www2.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 <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.

BibTeX citation:

@techreport{Subramonian:CSD-92-673,
    Author= {Subramonian, Ramesh},
    Title= {An O(log n) Time Common CRCW PRAM Algorithm for Minimum Spanning Tree},
    Year= {1992},
    Month= {Mar},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6133.html
%F Subramonian:CSD-92-673