Chapter 10. Graph Algorithms
Graph theory plays an important role in computer science because it provides an easy and systematic way to model many problems. Many problems can be expressed in terms of graphs, and can be solved using standard graph algorithms. This chapter presents parallel formulations of some important and fundamental graph algorithms.
Definitions and Representation
An undirected graph G is a pair (V, E), where V is a finite set of points called vertices and E is a finite set of edges. An edge e ∊ E is an unordered pair (u, v), where u, v ∊ V. An edge (u, v) indicates that vertices u and v are connected. Similarly, a directed graph G, is a pair (V, E), where V is the set of vertices as we just defined, but an edge (u, v) ∊ E is ...