Дерево доминаторов
Материал из WEGA
Дерево доминаторов (Dominator tree) — корневое ордерево, вершины которого суть вершины исходного графа и в котором дуга [math]\displaystyle{ (v,w) }[/math] существует в том и только том случае, когда [math]\displaystyle{ v }[/math] есть непосредственный обязательный предшественник (доминатор) вершины [math]\displaystyle{ w }[/math].
Другие названия — Доминаторное дерево, Дерево обязательного предшествования.
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
- Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.
