Dominator (grafteori)

1  dom          3  4  5  6 2  dom              3  dom                  4  dom                  5  dom                  6  dom                  Korresponderende dominator-relasjoner  er ikke strengt dominert  er umiddelbart dominert
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  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.

Referanser

Kategori:Grafteori
Kategori:Kompilatorer