<< Prev | - Up - | Next >> |

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 and in the graph there exists only a 4 relative positions into which they can be configured in the final tree.

, they become equal

, strictly dominates

, strictly dominates

, 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.

<< Prev | - Up - | Next >> |

Denys Duchier, Claire Gardent and Joachim Niehren

Version 1.2.4 (20020829)