Concurrent threads and optimal parallel minimum spanning trees algorithm

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 bits 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.