Dynamic Dominators in Practice

We consider the problem of dynamically maintaining a dominator tree of a flow graph, through a sequence of arc updates (insertions and deletions). We propose a new algorithm for this problem, which is based on the static dominators algorithm of Lengauer and Tarjan. Although the worst case complexity of a single update matches the running time of Lengauer-Tarjan, we exhibit the efficiency of our algorithm in practice.