# Difference between revisions of "Graph traversal"

From Rodinia

Line 1: | Line 1: | ||

− | |||

− | |||

Graph algorithms are fundamental and widely used in many disciplines and application | Graph algorithms are fundamental and widely used in many disciplines and application | ||

areas. Large graphs involving millions of vertices are common in scientific and | areas. Large graphs involving millions of vertices are common in scientific and | ||

engineering applications. | engineering applications. | ||

+ | This benchmark suite provides the GPU implementations of breadth-first search (BFS) algorithm which traverses all the connected components in a graph as well as single source shortest path algorithm (SSSP) which finds the smallest combined weight of edges between nodes. | ||

+ | |||

## Revision as of 04:01, 19 November 2008

Graph algorithms are fundamental and widely used in many disciplines and application areas. Large graphs involving millions of vertices are common in scientific and engineering applications. This benchmark suite provides the GPU implementations of breadth-first search (BFS) algorithm which traverses all the connected components in a graph as well as single source shortest path algorithm (SSSP) which finds the smallest combined weight of edges between nodes.

The breadth-first search and shortest path CUDA implementations can be downloaded from here

We would like to acknowledge Pawan Harish and P.J.Narayanan at IIIT who contributed their code to the Rodinia benchmark suite. The related paper can be found at here