Dominator (graph theory)

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 ni such that d dominates an immediate predecessor of ni, but d does not strictly dominate ni. 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.