16.2.4 A Generate and Test Algorithm

In the graph metaphor, solving a dominance constraint means to configure its the nodes of the constraint graph into a tree, such that all required dominance relations hold.

There exists a simple but naive `generate and test' algorithm doing this. The idea is that for any two nodes N_1 and N_2 in the graph there exists only a 4 relative positions into which they can be configured in the final tree.

$N_1 \gleich N_2$ , they become equal
$N_1 \domplus N_2$ , strictly dominates
$N_2 \domplus N_1$ , strictly dominates
$N_1 \bot N_2$ , is to the side of (i. e. none of the above).

We can thus decide the satisfiablity of a domiance constraint as follows: First guess one of the above relationsships for each two nodes in a graph. Then test, whether the graph satisfies all relationships required by the constraint and whether the graph augmented with the guessed relationships becomes tree-like. If one guess is consistent then the constraint graph is satisfiable, otherwise not.