Ramesh Subramonian

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-673
March 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 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://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