Paper ID: 8028
Exploring the use of constraint programming for enforcing connectivity during graph generation
The Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Page Numbers :
We discuss the problem of using constraint models to force generated graphs to be connected. We represent the graph as a simple adjacency matrix and then attempt to post constraints ensuring connectivity. Doing this using standard modelling primitives is harder than expected, because of our use of the implication operator. We develop a global constraint, "connected-graph", and show that it does save time over a class of graph generation problems, but most of the gains come from simple pre-search filters applied to insoluble instances. We finish by discussing a new constraint, "graphical", which simply ensures that a partially instantiated graph can be completed.