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 eE is an unordered pair (u, v), where u, vV. 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 ...

Get Introduction to Parallel Computing, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.