Dominator (graph theory)

1	dom	1	2	3	4	5	6
2	dom		2	3	4	5	6
3	dom			3
4	dom				4
5	dom					5
6	dom						6
Corresponding domination relation: Grey nodes are not strictly dominated Red nodes are immediately dominated

In computer science, a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$ . Notationally, this is written as $d dom n$ (or sometimes $d ≫ n$ ). By definition, every node dominates itself.

There are a number of related concepts:

A node $d$ strictly dominates a node $n$ if $d$ dominates $n$ and $d$ does not equal $n$ .
The immediate dominator or idom of a node $n$ is the unique node that strictly dominates $n$ but does not strictly dominate any other node that strictly dominates $n$ . Every node reachable from the entry node has an immediate dominator (except the entry node).
The dominance frontier of a node $d$ is the set of all nodes $n i$ such that $d$ dominates an immediate predecessor of $n i$ , but $d$ does not strictly dominate $n i$ . It is the set of nodes where $d$ 's dominance stops.
A dominator tree is a tree where each node's children are those nodes it immediately dominates. The start node is the root of the tree.