Presentation
Poster 2: An Efficient Parallel Algorithm for Dominator Detection
Event Type
ACM Student Research Competition: Graduate Posters
ACM Student Research Competition: Undergraduate Posters
Posters
TP
EX
EXH
Student Program
TimeThursday, 21 November 20198:30am - 5pm
LocationE Concourse
DescriptionIn 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.
Archive
