Visa påGitHub
- Depth-first-search
- A vertex dominates another vertex if it is only reachable through it.
- a. Successor - arch between u and v, meaning v is a successor to u succ(u) the set of vertices found after u where there is an arc between u and v
- a. ancestor in tree b. can't be an ancestor to itself c. descendant in tree d. can't be a descendant to itself
- Monotonic, i.e. either it doesn't change or the set of dominators decreases, resulting in termination
- Immediate predecessor in DT
- Remove w, compare two dominators, remove the one which dominates the other, repeat untill one left
- Semidominator is