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}
}
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