Rooted Tree and Spanning Tree Constraints
Patrick Prosser, Chris Unsworth · 2006
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.