Computing connected components on parallel computers

DOI10.1145/359138.359141MaRDI QIDQ3867197zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

connected components on an undirected graphparallel algorithmparallel processingtransitive closure of a symmetric Boolean matrix

Mathematics Subject Classification ID

Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(33)

• 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
• Efficient connection processing in equation-based object-oriented models
• Fast connected-component labeling
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• 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
• Optimal parallel algorithms on planar graphs
• A parallel algorithm for channel routing
• 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

This page was built for publication: Computing connected components on parallel computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3867197)