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

Материал из WikiGrapp

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

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

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/88],

[Свами-Тхуласимаран]