Dominator Tree Verification and Vertex-Disjoint Paths

Loukas Georgiadis and Robert E. Tarjan

Abstract

We present a linear-time algorithm that given a flowgraph $G=(V,A,r)$ and a tree $T$, checks whether $T$ is the dominator tree of $G$. Also we prove that there exist two spanning trees of $G$, $T_1$ and $T_2$, such that for any vertex $v$ the paths from $r$ to $v$ in $T_1$ and $T_2$ intersect only at the vertices that dominate $v$. The proof is constructive and our algorithm can build the two spanning trees in linear time. Simpler versions of our two algorithms run in $O(m \alpha(m,n))$-time, where $n$ is the number of vertices and $m$ is the number of arcs in $G$. The existence of such two spanning trees implies that we can order the calculations of the iterative algorithm for finding dominators, proposed by Allen and Cocke, so that it builds the dominator tree in a single iteration.