Paper ID: 8204
Rooted Tree and Spanning Tree Constraints
17th ECAI Workshop on Modelling and Solving Problems with Constraints
Page Numbers :
We present two specialised constraints for modelling trees. The first constrains a set of variables,
such that each variable takes as a value the index of its parent variable, with the exception of one
variable that takes as a value its own index and becomes the root, and this results in a rooted tree.
The second constraint assumes that constrained variables represent edges (or multi-edges) in a graph (or
multi-graph). Edges may be selected or rejected by a search process, and the constraint ensures that this
process results in a spanning tree. We also present a simple graph connectivity constraint and
a no-cycle constraint.
Keywords: constraints graph connectivity tree rooted spanning