Efficient parallel algorithms for graph problems

DOI10.1007/BF01840376MaRDI QIDQ1262781zbMATH OpenFDO

Authors Clyde Kruskal, Larry Rudolph, Marc Snir

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

spanning treesgraph algorithmsparallel algorithmsconnected componentsminimum spanning treesEREWbiconnected componentstree computationlinear speedupradix sort

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Theory of operating systems (68N25)

Recommendations

• scientific article; zbMATH DE number 3972201
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• scientific article; zbMATH DE number 4068310
• scientific article; zbMATH DE number 3905859
• Efficient parallel algorithms for series parallel graphs
• Parallel graph algorithms that are efficients on average
• Efficient parallel algorithms for path problems in directed graphs
• Parallel computations on graphs
• Parallel algorithms for connectivity problems in graph theory
• Efficient Parallel Algorithms for Chordal Graphs

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3635515 (Why is no real title available?)
• Finding Minimum Spanning Trees
• Parallel Prefix Computation
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Ultracomputers

Cited in

(33)

• Parallel algorithms for connectivity problems in graph theory
• More efficient parallel flow algorithms
• On parallel integer sorting
• scientific article; zbMATH DE number 4033068 (Why is no real title available?)
• A time-optimal solution for the path cover problem on cographs.
• Optimal parallel colouring algorithms for totally decomposable graphs
• scientific article; zbMATH DE number 4049080 (Why is no real title available?)
• scientific article; zbMATH DE number 3930349 (Why is no real title available?)
• scientific article; zbMATH DE number 4068310 (Why is no real title available?)
• scientific article; zbMATH DE number 4128411 (Why is no real title available?)
• Parallel Algorithm for Conflict Graph on OTIS-Triangular Array
• Improved parallel integer sorting without concurrent writing
• scientific article; zbMATH DE number 500370 (Why is no real title available?)
• Nearly work-efficient parallel algorithm for digraph reachability
• AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
• THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†
• Parallel algorithms for series parallel graphs
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• scientific article; zbMATH DE number 1102788 (Why is no real title available?)
• scientific article; zbMATH DE number 1985710 (Why is no real title available?)
• Optimal parallel quicksort on EREW PRAM
• High Parallel Complexity Graphs and Memory-Hard Functions
• Radix sort on the hypercube
• Efficient parallel algorithms for permutation graphs
• scientific article; zbMATH DE number 4087453 (Why is no real title available?)
• Parallel tree pattern matching
• Computational Science - ICCS 2004
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Efficient parallel graph algorithms for coarse-grained multicomputers and BSP
• Designing efficient parallel algorithms on interval graphs
• scientific article; zbMATH DE number 3972201 (Why is no real title available?)
• Experimental and Efficient Algorithms

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

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