Parallel algorithms for the connected components and minimal spanning tree problems

DOI10.1016/0020-0190(82)90131-4MaRDI QIDQ1162158zbMATH OpenOpenAlexFDO

Authors Dhruva Nath, S. N. Maheshwari

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90131-4

Mathematics Subject Classification ID

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

Cites work

• Computing connected components on parallel computers
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• scientific article; zbMATH DE number 3821102 (Why is no real title available?)
• Parallel Processing with the Perfect Shuffle

Cited in

(16)

• An adaptive and cost-optimal parallel algorithm for minimum spanning trees
• Determining connected components in linear time by a linear number of processors
• A randomized NC algorithm for the maximal tree cover problem
• Static and dynamic parallel computation of connected components
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations
• Parallel algorithms for the domination problems in trapezoid graphs
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Efficient minimum spanning tree algorithms on the reconfigurable mesh
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
• 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
• Optimal parallel algorithms on planar graphs
• Efficient parallel term matching and anti-unification
• Graph algorithms on a tree-structured parallel computer

This page was built for publication: Parallel algorithms for the connected components and minimal spanning tree problems

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