Dominator (graph Theory) - Algorithms

Algorithms

The dominators of a node n are given by the maximal solution to the following data-flow equations:

where is the start node.

The dominator of the start node is the start node itself. The set of dominators for any other node n is the intersection of the set of dominators for all predecessors p of n. The node n is also in the set of dominators for n.

An algorithm for direct solution is:

// dominator of the start node is the start itself Dom(n₀) = {n₀} // for all other nodes, set all nodes as the dominators for each n in N - {n₀} Dom(n) = N; // iteratively eliminate nodes that are not dominators while changes in any Dom(n) for each n in N - {n₀}: Dom(n) = {n} union with intersection over Dom(p) for all p in pred(n)

Direct solution is quadratic in the number of nodes, or O(n2). Lengauer and Tarjan developed an algorithm which is almost linear, but its implementation tends to be complex and time consuming for a graph of several hundred nodes or fewer.

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of Rice University describe an algorithm that essentially solves the above data flow equations but uses well engineered data structures to improve performance.