A Simple and Optimal Algorithm for Finding Immediate Dominators in Reducible Graphs

We present two simple algorithm for finding immediate dominator in reducible graphs with n nodes and m edges: A O(n + m) RAM algorithm and a O(n +m log log n) pointer machine algorithm. 1 Introduction Algorithms for finding dominator trees for control flow graphs are described in [5, 7, 8]. Dominator trees are used in control flow analysis [1, 4]. In [5] a linear time algorithm is given. This algorithm is complicated and to our knowledge no experimental results using this algorithm have been published. This is the motivation for presenting two simpler algorithms, one of which runs on a pointer machine [10]. The algorithms presented in this paper have previously been described by the authors of this paper and also independently and simultaneously in [9]. But at that time the important results from [2, 3], were not applied, so the contribution of this paper is only a compilation. 2 Notation A control flow graph CFG(V;E; s) is a directed graph with a start node s, from which all nodes i..