Dominator tree

Dominator tree --- дерево доминаторов, доминаторное дерево.

The dominator tree [math]\displaystyle{ T_{D} }[/math] of a dag [math]\displaystyle{ G }[/math] is a concise representation of the dominance relationship, where, for each vertex [math]\displaystyle{ x }[/math] in [math]\displaystyle{ G }[/math], the parent of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ T_{D} }[/math] corresponds to [math]\displaystyle{ DOM(x) }[/math]. Hence, a vertex [math]\displaystyle{ x }[/math] dominates a vertex [math]\displaystyle{ y }[/math] in [math]\displaystyle{ G }[/math] iff [math]\displaystyle{ x }[/math] is an ancestor of [math]\displaystyle{ y }[/math] in [math]\displaystyle{ T_{D} }[/math]. Given a set [math]\displaystyle{ U \subseteq V }[/math], a vertex [math]\displaystyle{ d \in V }[/math] is the nearest common dominator of [math]\displaystyle{ U }[/math] if the following two conditions hold: (1) [math]\displaystyle{ d }[/math] dominates all vertices of [math]\displaystyle{ U }[/math]; (2) there is no vertex [math]\displaystyle{ d' \neq d }[/math] that dominates all vertices of [math]\displaystyle{ U }[/math] and is dominated by [math]\displaystyle{ d }[/math].