Poster 2: An Efficient Parallel Algorithm for Dominator Detection

Student: Daniel Giger (University of Massachusetts, Lowell), Hang Liu (Stevens Institute of Technology)
Supervisor: Hang Liu (Stevens Institute of Technology)

Abstract: In graph theory, a vertex v dominates a vertex u if every path from the entry vertex to u must go through vertex v. This algorithm is called dominator detection and holds a wide range of applications, such as compiler design, circuit testing, and social network analysis. While the performance of many other graph algorithms soars with respect to the increase of the hardware parallelism, dominator detection algorithm experiences very little advancement due to the hardship of parallelism. This work thus introduces an efficient parallel dominator detection algorithm that is inspired by Breadth-First Search (BFS), which bests SEMI-NCA on large graphs.

ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing