Computing connected components on parallel computers
From MaRDI portal
Publication:3867197
DOI10.1145/359138.359141zbMath0429.68061MaRDI 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 algorithm; parallel processing; connected components on an undirected graph; transitive closure of a symmetric Boolean matrix
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68N25: Theory of operating systems
Related Items
Optimal parallel algorithms on planar graphs, Efficient parallel term matching and anti-unification, Resource bounds for parallel computation of threshold and symmetric functions, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, A parallel-design distributed-implementation (PDDI) general-purpose computer, Graph algorithms on a tree-structured parallel computer, An optimal parallel connectivity algorithm, Parallel recognition of complement reducible graphs and cotree construction, A parallel algorithm for the monadic unification problem, Separation and lower bounds for ROM and nondeterministic models of parallel computation, 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, Parallel algorithms for the single source shortest path problem, Parallel algorithms for the connected components and minimal spanning tree problems, Expected parallel time and sequential space complexity of graph and digraph problems, 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, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Efficient enumeration of all minimal separators in a graph, Improving the efficiency of parallel minimum spanning tree algorithms, Parallel approximation schemes for problems on planar graphs, Fast connected-component labeling, On the parallel computation of the biconnected and strongly connected co-components of graphs, Parallel computations on graphs, New fast parallel algorithm for the connected component problem and its VLSI implementation, On the Strongly Connected and Biconnected Components of the Complement of Graphs, IMPLEMENTING HIRSCHBERG'S PRAM-ALGORITHM FOR CONNECTED COMPONENTS ON A GLOBAL CELLULAR AUTOMATON, Parallel algorithms on graphs
