Concurrent threads and optimal parallel minimum spanning trees algorithm

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 sp anning trees in 0(log n) time. Specifically, we present a new algorithm to solve these problems in 0(log n) time using a linear number of processors o n the exclusive-read exclusive-write PRAM. The logarithmic time bound is ac tually optimal since it is well known that even computing the "OR" of n bit s requires Omega (log n) time on the exclusive-write PRAM. The efficiency a chieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.