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.
