An efficient and fast parallel-connected component algorithm

DOI10.1145/79147.214077MaRDI QIDQ3477960zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yijie Han, Robert A. Wagner

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/79147.214077

zbMATH Keywords

algorithmscomputation on discrete structuresconnectivitydata structures graphsgraphoptimal algorithmsparallel algorithm

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• New fast parallel algorithm for the connected component problem and its VLSI implementation
• scientific article; zbMATH DE number 3930349
• Static and dynamic parallel computation of connected components
• scientific article; zbMATH DE number 1057772
• An Efficient Parallel Biconnectivity Algorithm
• scientific article; zbMATH DE number 1844551
• Parallel algorithms for finding connected components of a graph
• An optimal parallel connectivity algorithm
• An optimal parallel co-connectivity algorithm

Cited in

(32)

• Determining connected components in linear time by a linear number of processors
• Parallel asynchronous connected components in a mesh
• I/O- and CPU-optimal recognition of strongly connected components
• Static and dynamic parallel computation of connected components
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Work-efficient parallel union-find with applications to incremental graph connectivity
• An optimal parallel co-connectivity algorithm
• Estimating the number of connected components in sublinear time
• Comparative study and proof of single-pass connected components algorithms
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• Finding strongly connected components in distributed graphs
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• A Fast Parallel Horner Algorithm
• scientific article; zbMATH DE number 4155927 (Why is no real title available?)
• An Efficient Parallel Biconnectivity Algorithm
• Equivalence in the complexity of several problems
• Finding Triconnected Components by Local Replacement
• Fast Connected Components Algorithms for the EREW PRAM
• scientific article; zbMATH DE number 1304268 (Why is no real title available?)
• A Simpler Parallel Algorithm for Graph Connectivity
• scientific article; zbMATH DE number 1057771 (Why is no real title available?)
• scientific article; zbMATH DE number 1057773 (Why is no real title available?)
• scientific article; zbMATH DE number 1751891 (Why is no real title available?)
• A Very Fast Algorithm for Simultaneously Performing Connected-Component Labeling and Euler Number Computing
• Graph connectivity in log steps using label propagation
• Euro-Par 2004 Parallel Processing
• Algorithm Theory - SWAT 2004
• Simple concurrent labeling algorithms for connected components
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• An optimal parallel connectivity algorithm
• A numerical algorithm for zero counting. I: Complexity and accuracy

This page was built for publication: An efficient and fast parallel-connected component algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3477960)