Concurrent determination of connected components

The design is described of a parallel version of Tarjan's algorithm for the determination of equivalence classes in graphs that represent images. Dist ribution of the vertices of the graph over a number of processes leads to a message passing algorithm. The algorithm is mapped to a shared-memory arch itecture by means of POSIX threads. It is applied to the determination of c onnected components in image processing. Experiments show a satisfactory sp eedup for sufficiently large images. (C) 2001 Elsevier Science B.V. All rig hts reserved.