Parallel graph algorithms. (c2000)

Abstract

One way the early use of parallel computers has resembled the early use of sequential computers has been the emphasis on numerical algorithms. However, as the field of parallel algorithms matures, the emphasis can be expected to shift to nonnumerical algorithms because more and more problems being solved on computers are symbolic in nature. This document examines a number of parallel algorithms developed to solve problems in graph theory. These problems relate to shortest paths in graphs and minimum-cost spanning trees. Chapter four is devoted to Moore's algorithm thus, it presents two parallel algorithms, one for solving the single-source shortest path (SSSP) problem and the second solve the all pairs shortest path (APSP) problem. Our focus in chapter five is on Dijkstra's algorithm; first, we describe the sequential SSSP algorithm, then we present a parallel formulation for solving APSP problems. Chapter six presents Prim's graph algorithm for computing the minimum spanning tree.