Efficient parallel algorithms for some graph problems

DOI10.1145/358628.358650MaRDI QIDQ3945594zbMATH OpenOpenAlexFDO

Authors John Lam, I-Ngo Chen, 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 algorithmsoptimal algorithmsmultiprocessorssingle 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)

Cited in

(33)

• Finding fundamental cycles and bridges on a tree-structured parallel computer
• An efficient parallel algorithm for updating minimum spanning trees
• An I/O efficient algorithm for minimum spanning trees
• On handling vertex deletion in updating minimum spanning trees
• Determining connected components in linear time by a linear number of processors
• Improving the efficiency of parallel minimum spanning tree algorithms
• Optimal parallel algorithms on planar graphs
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• A complexity theory of efficient parallel algorithms
• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Computing minimum spanning forests on 1- and 2-dimensional processor arrays (extended abstract)
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• A parallel-design distributed-implementation (PDDI) general-purpose computer
• Static and dynamic parallel computation of connected components
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• An optimal parallel algorithm for minimum spanning trees in planar graphs
• Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
• An adaptive and cost-optimal parallel algorithm for minimum spanning trees
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Expected parallel time and sequential space complexity of graph and digraph problems
• Graph algorithms on a tree-structured parallel computer
• An optimal parallel processor bound in strong orientation of an undirected graph
• IMPLEMENTING HIRSCHBERG'S PRAM-ALGORITHM FOR CONNECTED COMPONENTS ON A GLOBAL CELLULAR AUTOMATON
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• Parallel computations on graphs
• Algorithms for some graph problems on a distributed computational model
• Oblivious algorithms for multicores and networks of processors
• Optimal speed-up algorithms for template matching on SIMD hypercube multiprocessors with restricted local memory
• SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
• A new class of parallel algorithms for finding connected components on machines with bit-vector operations

This page was built for publication: Efficient parallel algorithms for some graph problems

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