Efficient parallel algorithms for some graph problems

DOI10.1145/358628.358650zbMath0485.68056OpenAlexW2069446854MaRDI QIDQ3945594

I-Ngo Chen, John Lam, Francis Y. L. Chin

Publication date: 1982

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358628.358650

zbMATH Keywords

analysis of algorithmsmultiprocessorsoptimal algorithmssingle instruction stream-multiple data stream modeltradeoffs among complexity measures

Mathematics Subject Classification ID

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, Optimal parallel algorithms for multiple updates of minimum spanning trees, Finding fundamental cycles and bridges on a tree-structured parallel computer, 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, On handling vertex deletion in updating minimum spanning trees, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, An efficient parallel algorithm for updating minimum spanning trees, An I/O Efficient Algorithm for Minimum Spanning Trees, Determining connected components in linear time by a linear number of processors, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Computing minimum spanning forests on 1- and 2-dimensional processor arrays, Parallel computations on graphs, Oblivious algorithms for multicores and networks of processors, A complexity theory of efficient parallel algorithms, Optimal speed-up algorithms for template matching on SIMD hypercube multiprocessors with restricted local memory, Expected parallel time and sequential space complexity of graph and digraph problems, Efficient parallel algorithms for doubly convex-bipartite graphs, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Algorithms for some graph problems on a distributed computational model, 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, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, A parallel-design distributed-implementation (PDDI) general-purpose computer, Graph algorithms on a tree-structured parallel computer, An adaptive and cost-optimal parallel algorithm for minimum spanning trees, An optimal parallel processor bound in strong orientation of an undirected graph, On the Strongly Connected and Biconnected Components of the Complement of Graphs, Improving the efficiency of parallel minimum spanning tree algorithms, Static and dynamic parallel computation of connected components