Dominator (grafteori)

1	dom	1	2	3	4	5	6
2	dom		2	3	4	5	6
3	dom			3
4	dom				4
5	dom					5
6	dom						6
Korresponderende dominator-relasjoner
Grå noder er ikke strengt dominert
Røde noder er umiddelbart dominert

Eksempel på en kontrollflytgraf med inngangsnode 1.

En dominator er innen informatikken en spesiell type kontrollflytgraf hvor en node d dominerer en node n hvis enhver sti fra inngangsnoden til n må gå gjennom d. Dette betegnes som d dom n, eller noen ganger som d $\gg$ n. Enhver node dominerer per definisjon seg selv.

Det finnes en rekke relaterte konsepter:

• En node d dominerer strengt en node n hvis d dominerer n og d ikke er lik n.
• Den umiddelbare dominator eller idom til en node n er den unike node som strengt dominerer n men ikke strengt dominerer noen annen node som strengt dominerer n. Enhver node, bortsett fra inngangsnoden, har en umiddelbar dominator.
• Dominance frontier til en node d er mengden med noder n slik at d dominerer en umiddelbar forgjenger til n, mens d ikke strengt dominerer n. Det er mengden med noder hvor d's dominans stanser.
• Et dominatortre er et tre hvor hver node's barn er de noder det umiddelbart dominerer. Fordi den umiddelbare dominator er unik, er det et tre. Startnoden er roten til treet.