Parallel graph algorithms

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 of architectures.