Treedominance

Treedominance is a concept in graph theory that captures which nodes in a directed graph must be traversed to reach other nodes from a designated entry node. A node d treedominates a node n if every possible path from the entry node to n passes through d. The immediate treedominator of n, denoted idom(n), is the closest strict dominator of n. The structure formed by linking each node n (except the entry) to its immediate dominator idom(n) is the treedominance tree, also known as the dominator tree, rooted at the entry node.

Construction and algorithms for treedominance involve computing idom(n) for all nodes reachable from the entry. The resulting parent relation defines a tree in which, for any node, the path from the root to that node lists all its dominators. Efficient algorithms exist, with the Lengauer–Tarjan method providing near-linear time performance for general flow graphs. Simpler approaches can be used for acyclic graphs or smaller graphs.

Key properties include the transitivity of dominance: if d treedominates n and e treedominates d, then e treedominates n. The dominator tree encodes all dominator relationships compactly, and the root of the tree dominates every node reachable from the entry. By traversing from the root to a node in the tree, one obtains its complete set of dominators.

Example: Consider a graph with entry S and nodes A, B, C, D, E and edges S→A, S→B, S→C, A→D, B→D, C→D, D→E. All paths to A, B, and C pass through S, so idom(A)=S, idom(B)=S, idom(C)=S. All paths to D pass through S as well, so idom(D)=S, while E is reached only through D, giving idom(E)=D. The domi­nator tree has S as root with children A, B, C, D, and E as a child of D.

Applications of treedominance include compiler optimization, program analysis, and static data-flow analysis, where dominance relations help determine safe code motion, control dependence, and program slicing. See also dominators in graph theory and dominator trees.