Efficient Parallel Algorithm for the Connected Component Problem and Its Implementation on the DPP84 (Delft Parallel Processor)

摘要

The report describes an algorithm for determining the connected components of a simple undirected graph with n nodes using O(n) time and n processors. It requires a Shared Memory SIMD model permitting simultaneous reading from the same memory location by different processors (read conflicts). Its implementation on the DPP 84 (the Delft Parallel Processor) and related problems are described. (Copyright (c) 1986 by Faculty of Mathematics and Informatics, Delft, The Netherlands.)