Thumbnail
Access Restriction
Subscribed

Author Chong, Ka Wong ♦ Han, Yijie ♦ Lam, Tak Wah
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword EREW PRAM ♦ Connected components ♦ Minimum spanning trees ♦ Parallel algorithms
Abstract This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in $\textit{O}(log\textit{n})$ time. Specifically, we present a new algorithm to solve these problems in $\textit{O}(log\textit{n})$ time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the “OR” of $\textit{n}bit$ requires &OHgr;(log $\textit{n}$ time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 2
Page Count 27
Starting Page 297
Ending Page 323


Open content in new tab

   Open content in new tab
Source: ACM Digital Library