An efficient and fast parallel-connected component algorithm

DOI10.1145/79147.214077zbMATH0699.68064DBLPjournals/jacm/HanW90OpenAlexW1993297915WikidataQ56518875MaRDI QIDQ3477960FDOQ3477960

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)

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