Дерево доминаторов

Дерево доминаторов (Dominator tree) — корневое ордерево, вершины которого суть вершины исходного графа и в котором дуга [math]\displaystyle{ (v,w) }[/math] существует в том и только том случае, когда [math]\displaystyle{ v }[/math] есть непосредственный обязательный предшественник (доминатор) вершины [math]\displaystyle{ w }[/math].

Другие названия — Доминаторное дерево, Дерево обязательного предшествования.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

• Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.