 {| style="float:right" class=wikitable |- ! 1 | dom &nbsp; &nbsp; ||  ||  || 3 || 4 || 5 || 6 |- ! 2 | dom || ||  ||  ||  ||  ||  |- ! 3 | dom || || ||  || || || |- ! 4 | dom || || || ||  || || |- ! 5 | dom || || || || ||  || |- ! 6 | dom || || || || || ||  |- | colspan=8 | corresponding domination relation |- | colspan=8 |  are not strictly dominated |- | colspan=8 |  are immediately dominated |} {| style="float:right" | thumb|200px|example control flow graph with entry node 1. |} in computer science, in control flow graphs, a node d dominates a node n if every path from the entry node to n must go through d. notationally, this is written as d dom n (or sometimes d \gg n). by definition, every node dominates itself. there are a number of related concepts: * a node d strictly dominates a node n if d dominates n and d does not equal n. * the immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. every node, except the entry node, has an immediate dominator. * the dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. it is the set of nodes where d's dominance stops. * a dominator tree is a tree where each node's children are those nodes it immediately dominates. because the immediate dominator is unique, it is a tree. the start node is the root of the tree. == history == dominance was first introduced by reese t. prosser in a 1959 paper on analysis of flow diagrams. prosser did not present an algorithm for computing dominance, which had to wait ten years for edward s. lowry and c. w. medlock.{{cite paper |title=object code optimization |url=http://portal.acm.org/ft_gateway.cfm?id=362838&type=pdf&coll=guide&dl=guide&cfid=79528182&cftoken=33765747 |journal=communications of the acm |volume=12 |issue=1 |date=january 1969 |pages=13â22 |first=edward s. |last=lowry |author2=medlock, 
Compiler_construction Graph_theory