Efficient parallel algorithms for graph problems

DOI10.1007/BF01840376zbMath0686.68055MaRDI QIDQ1262781

Marc Snir, Clyde P. Kruskal, Larry Rudolph

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

connected componentsparallel algorithmsgraph algorithmsradix sortminimum spanning treesspanning treesEREWbiconnected componentstree computationlinear speedup

Mathematics Subject Classification ID

Related Items (11)

Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS ⋮ Improved parallel integer sorting without concurrent writing ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗† ⋮ Optimal parallel colouring algorithms for totally decomposable graphs ⋮ A time-optimal solution for the path cover problem on cographs. ⋮ Parallel tree pattern matching ⋮ Radix sort on the hypercube ⋮ Optimal parallel quicksort on EREW PRAM ⋮ On parallel integer sorting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Parallel Prefix Computation
• Ultracomputers
• Finding Minimum Spanning Trees

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