Abstract
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 language | English |
|---|---|
| Pages (from-to) | 173-194 |
| Number of pages | 22 |
| Journal | Science of computer programming |
| Volume | 41 |
| Issue number | 2 |
| Publication status | Published - Oct-2001 |
Keywords
- connected components
- parallel algorithm
- pthreads
- mutex
- condition variable
- ALGORITHMS