Computing at Glasgow University
Paper ID: 8204

Rooted Tree and Spanning Tree Constraints
Unsworth,C. Prosser,P.

Publication Type: Other
Appeared in: 17th ECAI Workshop on Modelling and Solving Problems with Constraints
Page Numbers :
Publisher: N/A
Year: 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.

Keywords: constraints graph connectivity tree rooted spanning

PS/PS.GZ PDF Bibtex entry Endnote XML