An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph

DOI10.1137/0220066zbMath0738.68062OpenAlexW2125182537WikidataQ56271078 ScholiaQ56271078MaRDI QIDQ3985808

Hillel Gazit

Publication date: 27 June 1992

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

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

zbMATH Keywords

connected componentsCRCWparallel randomized algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Connectivity (05C40)

Related Items

Finding small simple cycle separators for 2-connected planar graphs, Planarity testing in parallel, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH, Efficient algorithmic learning of the structure of permutation groups by examples, Unnamed Item