What's on in Computing Science?

Date: Tuesday, 13 December, 2005
Time: 16:00
Location: F121 conference room
Constraint programming for enforcing graph connectivity
Patrick Prosser University of Glasgow
Exploring the use of constraint programming for enforcing connectivity during graph generation

There are many cases where we are to produce a graph (a collection of vertices and edges) that is connected (i.e. there is a path between any pair of vertices). There might be some side constraints associated with this, such as the degree of vertices (the number of edges incident on a vertex), or edges that are disallowed, disjunctive edges (such as edges that are not allowed to cross), and maximum or minimum distances between vertices. Such real world examples come from computational chemistry, bioinformatics, network design, and transportation problems. In my talk I will present three constraint programming models for the connectivity constraint and discuss future work. The graph is represented as a simple adjacency matrix of 0/1 constrained integer variables and constraints are posted to ensure connectivity. A process is then at liberty to select and reject edges. This is ongoing work with Ken Brown (Cork), Chris Beck (Toronto), Christine Wu (Cork), and Ian Miguel (St. Andrews)

Contact: Dr Alice A Miller (alice@dcs.gla.ac.uk)

URL: Constraint programming for enforcing graph connectivity

Add to my calendar