Concurrent determination of connected components

Hesselink, W. H., Meijster, A. & Bron, C., Oct-2001, In : Science of computer programming. 41, 2, p. 173-194 22 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard


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.

Original languageEnglish
Pages (from-to)173-194
Number of pages22
JournalScience of computer programming
Issue number2
Publication statusPublished - Oct-2001


  • connected components, parallel algorithm, pthreads, mutex, condition variable, ALGORITHMS

Download statistics

No data available

ID: 3108185