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(Vlog 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 + Elog E) time bound of a known algorithm for finding dominators in reducible graphs. If E Vlog V, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.