Concurrent determination of connected components

OnderzoeksoutputAcademicpeer review

10 Citaten (Scopus)
281 Downloads (Pure)


The design is described of a parallel version of Tarjan's algorithm for the determination of equivalence classes in graphs that represent images. Distribution 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 architecture by means of POSIX threads. It is applied to the determination of connected components in image processing. Experiments show a satisfactory speedup for sufficiently large images. (C) 2001 Elsevier Science B.V. All rights reserved.

Originele taal-2English
Pagina's (van-tot)173-194
Aantal pagina's22
TijdschriftScience of computer programming
Nummer van het tijdschrift2
StatusPublished - okt-2001

Citeer dit