Computing connected components on parallel computers
From MaRDI portal
Publication:3867197
DOI10.1145/359138.359141zbMath0429.68061OpenAlexW2086825382MaRDI QIDQ3867197
Ashok K. Chandra, Dilip V. Sarwate, Daniel S. Hirschberg
Publication date: 1979
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359138.359141
parallel algorithmparallel processingconnected components on an undirected graphtransitive closure of a symmetric Boolean matrix
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)
Related Items
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 ⋮ A parallel algorithm for the monadic unification problem ⋮ Separation and lower bounds for ROM and nondeterministic models of parallel computation ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM ⋮ Determining connected components in linear time by a linear number of processors ⋮ Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs ⋮ A linear systolic algorithm for the connected component problem ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Parallel approximation schemes for problems on planar graphs ⋮ Parallel computations on graphs ⋮ Efficient enumeration of all minimal separators in a graph ⋮ A parallel algorithm for channel routing ⋮ Parallel algorithms for the single source shortest path problem ⋮ Parallel algorithms for the connected components and minimal spanning tree problems ⋮ Parallel recognition of complement reducible graphs and cotree construction ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Efficient parallel term matching and anti-unification ⋮ Fast connected-component labeling ⋮ Optimal parallel algorithms on planar graphs ⋮ IMPLEMENTING HIRSCHBERG'S PRAM-ALGORITHM FOR CONNECTED COMPONENTS ON A GLOBAL CELLULAR AUTOMATON ⋮ New fast parallel algorithm for the connected component problem and its VLSI implementation ⋮ Resource bounds for parallel computation of threshold and symmetric functions ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Efficient connection processing in equation-based object-oriented models ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ Graph algorithms on a tree-structured parallel computer ⋮ An optimal parallel connectivity algorithm ⋮ Parallel algorithms on graphs ⋮ On the Strongly Connected and Biconnected Components of the Complement of Graphs ⋮ Improving the efficiency of parallel minimum spanning tree algorithms
