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

Материал из WikiGrapp

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

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

Литература

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