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

graphalgorithmsparallel algorithmconnectivityoptimal algorithmscomputation on discrete structuresdata structures graphs

Mathematics Subject Classification ID

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

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

(25)

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

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)