UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8028

Exploring the use of constraint programming for enforcing connectivity during graph generation
Brown,K.N. Prosser,P. Beck,J.C. Wu,C.W.

Publication Type: Conference Proceedings
Appeared in: The Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Page Numbers :
Publisher: N/A
Year: 2005
ISBN/ISSN:
Abstract:

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.


PS/PS.GZ Bibtex entry Endnote XML