Parallel algorithms for the connected components and minimal spanning tree problems

DOI10.1016/0020-0190(82)90131-4zbMath0479.68069OpenAlexW2033887412MaRDI QIDQ1162158

S. N. Maheshwari, Dhruva Nath

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)

Related Items

A new class of parallel algorithms for finding connected components on machines with bit-vector operations, On the parallel computation of the biconnected and strongly connected co-components of graphs, Parallel algorithms for the domination problems in trapezoid 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, Parallel computations on graphs, Efficient minimum spanning tree algorithms on the reconfigurable mesh, A randomized NC algorithm for the maximal tree cover problem, Efficient parallel term matching and anti-unification, Optimal parallel algorithms on planar graphs, New fast parallel algorithm for the connected component problem and its VLSI implementation, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, Graph algorithms on a tree-structured parallel computer, An adaptive and cost-optimal parallel algorithm for minimum spanning trees, On the Strongly Connected and Biconnected Components of the Complement of Graphs, Static and dynamic parallel computation of connected components

Cites Work

• Unnamed Item
• Computing connected components on parallel computers
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Parallel Processing with the Perfect Shuffle