Research indexJournal article
Concurrent threads and optimal parallel minimum spanning trees algorithm
Chong, Han, Lam
JACM1 Mar 2001
NobleIDark:/48914/w1/20260516/4E40179BDOI10.1145/375827.375847
Concurrent threads and optimal parallel minimum spanning trees algorithm
Chong, Han, Lam · JACM · 2001 · Subscription
NobleIDark:/48914/w1/20260516/4E40179BDOI10.1145/375827.375847
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
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 O (log n ) time. Specifically, we present a new algorithm to solve these problems in O (log 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 n bit requires Ω(log 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.