Optimal Parallel Algorithms for Interger Sorting and Graph Connectivity

摘要

This document gives new parallel algorithms for integer sorting and undirected graph connectivity problems such as connected components and spanning forest. These algorithms cost only logarithmic time and are the first known that are optimal: the product of their time and processor bounds are bounded by a linear function of the input size. All previous known parallel algorithms for these problems required at least a linear number of processors to achieve logarithmic time bounds, and hence were nonoptimal by at least a logarithmic factor. The author assumes a parallel random access machine (RAM) model which allows both concurrent writes and concurrent reads of global memory. The algorithms are randomized; each processor is allowed an independent random number generator; however our stated resource bounds hold for worst case input with overwhelming likelihood as the input size grows. (Author)