Doctoral seminars

< back

Tuesday 25 April 2006 at 14h00 in Celestijnenlaan 200 room S00.05

CP(Graph): A graph computation domain in Constraint Programming

By Yves Deville (Computing Science and Engineering Department, Universite Catholique de Louvain)

Abstract:

In an increasing number of domains such as bioinformatics, combinatorial graph problems arise. We propose a novel way to solve these problems. Our approach extends constraint programming by introducing CP(Graph), a computation domain focused on graphs including a new type of variable: graph domain variables as well as constraints over these variables and their propagators. CP(Graph) is integrated with finite domain and finite sets computation domains, allowing the combining of constraints of these domains with graph constraints. We also show how the integration of CP(Graph) and CP(Map) can be used for modeling and solving approximate graph matching as well as many other matching problems. These computation domains are now integrated in the Gecode constraint environment.