(Q) Parallel connected components problem

(Q) Parallel connected components problem

Post by Jeong Cheol J » Fri, 11 Nov 1994 10:42:23



Can anybody tell me the most recent determinstic parallel
algorithm for finding connected components and minimum spanning
forests? The assumed machine model is PRAM and I'd like to
know the algorithms with smallest cost of all.

Thanks in advance.
--

+-------------------------------------------------------+


 Software Engineering Division
 Systems Engineering Research Institute
 Korea Institute of Science and Technology

+-------------------------------------------------------+

 
 
 

1. PARALLEL ALGORITHMS FOR IMAGE HISTOGRAMMING AND CONNECTED COMPONENTS

ANNOUNCEMENT:

--------------------------------------------------------------------
PARALLEL ALGORITHMS FOR IMAGE HISTOGRAMMING AND CONNECTED COMPONENTS
                    WITH AN EXPERIMENTAL STUDY
--------------------------------------------------------------------

We have released our technical report entitled ``Parallel Algorithms
for Image Histogramming and Connected Components with an Experimental
Study,'' by David A. Bader and Joseph Ja'Ja'.  Technical Report
Number: CS-TR-3384 and UMIACS-TR-94-133.  Institute for Advanced
Computer Studies (UMIACS) and the Department of Electrical
Engineering, University of Maryland, College Park, December 1994.

The paper is available in PostScript format via WWW:

http://www.umiacs.umd.edu/~dbader

or via anonymous ftp to:

ftp.cs.umd.edu:/pub/papers/TRs/3384.ps.Z

If you prefer a hardcopy, please reply to this message and send me
your mailing address.

ABSTRACT:
This paper presents efficient and portable implementations of two
useful primitives in image processing algorithms, histogramming and
connected components.  Our general framework is a single-address
space, distributed memory programming model.  We use efficient
techniques for distributing and coalescing data as well as efficient
combinations of task and data parallelism.  Our connected components
algorithm uses a novel approach for parallel merging which performs
drastically limited updating during iterative steps, and concludes
with a total consistency update at the final step. The algorithms have
been coded in Split-C and run on a variety of platforms.  Our
experimental results are consistent with the theoretical analysis and
provide the best known execution times for these two primitives, even
when compared with machine specific implementations.  More efficient
implementations of Split-C will likely result in even faster execution
times.

---
David A. Bader
Electrical Engineering Department
A.V. Williams Building
University of Maryland
College Park, MD 20742
Office: 301-405-6755  
FAX:    301-314-9658


WWW:      http://www.umiacs.umd.edu/~dbader

2. 8's turned into B's

3. Algorithms for Incremental Strongly Connected Components ?

4. QNX & power off without shutdown

5. strongly k-connected components

6. Very urgent Java Position in Boise, ID

7. Strongly connected components

8. CDROM in ITALY !!NEW ADDRESS!! SORRY!!!!!

9. Any Incremental Strongly Connected Component Algorithms?

10. Graphs: Nontrivial strongly connected components

11. Strongly Connect Components

12. dynamic maintenance of connected components

13. Connected components of AND/OR graphs