Computing at Glasgow University
Paper ID: 8205

A Connectivity Constraint using Bridges
Prosser,P. Unsworth,C.

Publication Type: Conference Proceedings
Appeared in: 17th European Conference on Artificial Intelligence (ECAI 2006)
Page Numbers :
Publisher: N/A
Year: 2006

We present a specialised constraint for enforcing graph connectivity. It is assumed that we have a square symmetrical array A of 0/1 constrained integer variables representing potential undirected edges in a simple graph, such that variable A[u,v] corresponds to the undirected edge (u,v). A search process is then at liberty to select and reject edges. The connectivity constraint ensures that no critical edge may be deleted from A, i.e. an edge that if deleted disconnects the graph. This connectivity constraint might then be used when modelling network design problems, modelling molecular structures, problems in bioinformatics, or graph problems where connectivity is an essential property.

Keywords: constraints graph connectivity bridge-connected

PS/PS.GZ PDF Bibtex entry Endnote XML