patternMinor
Dominator Tree for DAG
Viewed 0 times
dominatordagfortree
Problem
Is there a fast algorithm to compute dominator tree for acyclic graphs?
The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?
The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?
Solution
Recall the definition of dominators:
$$\hbox{Dom}(n_o) = \{ n_o \}$$
$$\hbox{Dom}(n) = \{ n \} \cup \bigcap_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$
This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.
It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.
$$\hbox{Dom}(n_o) = \{ n_o \}$$
$$\hbox{Dom}(n) = \{ n \} \cup \bigcap_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$
This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.
It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.
Context
StackExchange Computer Science Q#43105, answer score: 6
Revisions (0)
No revisions yet.