Dominator Tree — Lengauer-Tarjan

Flow graph → DFS numbering → semidominators → dominator tree, built step by step.

Naive O(V·E) LT simple O(E·log V) LT sophisticated O(E·α(V)) Space O(V+E)

Graph:

entry r DFS current computing sdom idom fixed idom edge

Flow Graph (left) | Dominator Tree (right)

SlowFast

Step Info

Press Start to run, or Step one phase at a time.

State

Phase—

Step0 / 0

idom fixed0

Big-O

Method	Time
Naive dataflow	O(V·E)
LT simple	O(E·log V)
LT sophisticated	O(E·α(V))
Query dom	O(1)*
Space	O(V+E)

Log