Finding Connected Components in O(log n log log n) Time on the EREW PRAM
DOI10.1006/JAGM.1995.1016zbMATH Open0834.68089OpenAlexW4249333804WikidataQ58063089 ScholiaQ58063089MaRDI QIDQ4837541FDOQ4837541
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
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Distributed algorithms (68W15)
Cited In (12)
- A Simpler Parallel Algorithm for Graph Connectivity
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Determining connected components in linear time by a linear number of processors
- Title not available (Why is that?)
- The interval-merging problem
- Graph connectivity in log steps using label propagation
- Edge-matching graph contractions and their interlacing properties
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- NC algorithms for weighted planar perfect matching and related problems
- A faster parallel connectivity algorithm on cographs
- Towards more precise parallel biconnectivity approximation
- Connectivity oracles for graphs subject to vertex failures
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)
