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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.