Parallel Processing

All-Pairs Shortest Paths

Instead of finding the shortest paths from a single vertex v to every other vertex, we are sometimes interested in finding the shortest paths between all pairs of vertices....

Single-Source Shortest Paths: Dijkstra’s Algorithm

For a weighted graph G = (V, E, w), the single-source shortest paths problem is to find the shortest paths from a vertex v V to all other vertices...

Minimum Spanning Tree: Prim’s Algorithm

A spanning tree of an undirected graph G is a subgraph of G that is a tree containing all the vertices of G. In a weighted graph, the weight...

Definitions and Representation of a graph

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

Quicksort

All the algorithms presented so far have worse sequential complexity than that of the lower bound for comparison-based sorting, Q(n log n). This section examines the quicksort algorithm, which...

Bubble Sort and its Variants

The previous section presented a sorting network that could sort n elements in a time of Q(log2 n). We now turn our attention to more traditional sorting algorithms. Since...

Sorting Networks

In the quest for fast sorting methods, a number of networks have been designed that sort n elements in time significantly smaller than Q(n log n). These sorting networks...

Issues in Sorting on Parallel Computers

Parallelizing a sequential sorting algorithm involves distributing the elements to be sorted onto the available processes. This process raises a number of issues that we must address in order...

Matrix-Matrix Multiplication

This section discusses parallel algorithms for multiplying two n x n dense, square matrices A and B to yield the product matrix C = A x B. All parallel...

Matrix-Vector Multiplication

This section addresses the problem of multiplying a dense n x n matrix A with an n x 1 vector x to yield the n x 1 result vector...