A Simple Dynamic Algorithm for Maintaining a Dominator Tree

We present a simple algorithm which maintains the dominator tree for an arbitrary flow graph during a sequence of i edge insertions interspersed with q queries as "does x dominate y?". The complexity of the algorithm is O(q + m minfi; ng), where m and n respectively are the number of edges and nodes in the flow graph after the i 0 th edge insertion. This improves the former best results from O(q log n +m i log n) in [13] and O(q n +m i) in [6]. Furthermore, we show that the complexity of our algorithm for a single edge insertion is bounded by those nodes which no longer will be dominated by the same set of nodes. 1 Introduction Dominator trees are used in control flow analysis [1, 7, 8, 9]. Algorithms for finding dominator trees for control flow graphs are given in [10, 11, 12] and the algorithm in [10] is linear. Recently dynamic algorithms [4, 6, 13] 1 have been presented for maintaining dominator trees, but the complexities of these algorithms are worse or just as good ..