An O(logn) parallel connectivity algorithm

DOI10.1016/0196-6774(82)90008-6zbMath0494.68070WikidataQ56813859 ScholiaQ56813859MaRDI QIDQ3957960

Uzi Vishkin, Yossi Shiloach

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90008-6

zbMATH Keywords

connected components of an undirected graph; synchronized parallel computation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C40: Connectivity

68N25: Theory of operating systems

Related Items

Efficient parallel algorithms for doubly convex-bipartite graphs, 1-Approximation algorithm for bottleneck disjoint path matching, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Efficient parallel algorithms to test square-freeness and factorize strings, Processor-time tradeoffs in PRAM simulations, Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers, Vectorized search for single clusters, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Static and dynamic parallel computation of connected components, A new class of parallel algorithms for finding connected components on machines with bit-vector operations, A parallel algorithm for computing Steiner trees in strongly chordal graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, A remark on maximum matching of line graphs, \(O(\log \log n)\)-time integer geometry on the CRCW PRAM, Sweep methods for parallel computational geometry, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Efficient algorithmic learning of the structure of permutation groups by examples, Efficient algorithms for acyclic colorings of graphs, Optimal parallel algorithms for multiple updates of minimum spanning trees, An nc algorithm to recognize hhd-free graphs