Finding Dominators in Directed Graphs

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of O (V V + E) if V is the number of vertices and E is the number of edges in the graph. This bound compares favorably with the O (V (V + E) ) time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the O (V + E E) time bound of a known algorithm for finding dominators in reducible graphs. If E V V, the new algorithm requires O (E) time and is optimal to within a constant factor.