Fast Connected Components Algorithms for the EREW PRAM

DOI10.1137/S009753979325247XMaRDI QIDQ4229421zbMATH OpenOpenAlexFDO

Authors Noam Nisan, Michal Parnas, David R. Karger

Publication date 22 February 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979325247x

zbMATH Keywords

connected componentsgraph algorithmsparallel algorithmsrandom walks

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Sums of independent random variables; random walks (60G50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• scientific article; zbMATH DE number 437524
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• An efficient and fast parallel-connected component algorithm

Cited in

(16)

• Static and dynamic parallel computation of connected components
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Active exploration for large graphs
• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• IMPLEMENTING HIRSCHBERG'S PRAM-ALGORITHM FOR CONNECTED COMPONENTS ON A GLOBAL CELLULAR AUTOMATON
• 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?)
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Graph connectivity in log steps using label propagation
• Many Random Walks Are Faster Than One
• Parallel algorithms for finding connected components of a graph
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
• Simple concurrent labeling algorithms for connected components
• An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM

This page was built for publication: Fast Connected Components Algorithms for the EREW PRAM

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