Parallel Depth First Search for Directed Acyclic Graphs

Depth-First Search (DFS) is a common algorithm, often used as a building block for topological sort, connectivity and planarity testing, among many other applications. We implemented the work-efficient parallel algorithm for the DFS traversal of directed acyclic graphs (DAGs) and reported the speedup of this parallel algorithm (in comparison with the serial implementation).

[PDF] [Code]