Report Number: CS-TR-84-1028
Institution: Stanford University, Department of Computer Science
Title: Parallel graph algorithms
Author: Hochschild, Peter H.
Author: Mayr, Ernst W.
Author: Siegel, Alan R.
Date: December 1984
Abstract: This paper presents new paradigms to solve efficiently a
variety of graph problems on parallel machines. These
paradigms make it possible to discover and exploit the
"parallelism" inherent in many classical graph problems. We
abandon attempts to force sequential algorithms into parallel
environments for such attempts usually result in transforming
a good uniprocessor algorithm into a hopelessly greedy
parallel algorithm. We show that by employing more local
computation and mild redundance, a variety of problems can be
solved in a resource- and time-efficient manner on a variety