Finding Connected Components in O(log n log log n) Time on the EREW PRAM

DOI10.1006/JAGM.1995.1016MaRDI QIDQ4837541zbMATH OpenOpenAlexWikidataFDO

Authors Ka Wong Chong, Tak-Wah Lam

Publication date 3 July 1995

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1995.1016

zbMATH Keywords

undirected graphEREW

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 437524
• Fast Connected Components Algorithms for the EREW PRAM
• 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
• An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM

Cited in

(13)

• A faster parallel connectivity algorithm on cographs
• NC algorithms for weighted planar perfect matching and related problems
• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An optimal parallel algorithm for minimum spanning trees in planar graphs
• Towards more precise parallel biconnectivity approximation
• A Simpler Parallel Algorithm for Graph Connectivity
• The interval-merging problem
• Connectivity oracles for graphs subject to vertex failures
• Graph connectivity in log steps using label propagation
• Edge-matching graph contractions and their interlacing properties
• Determining connected components in linear time by a linear number of processors
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM

This page was built for publication: Finding Connected Components in O(log n log log n) Time on the EREW PRAM

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