Result: CP(Graph) : Introducing a graph computation domain in constraint programming

Title:
CP(Graph) : Introducing a graph computation domain in constraint programming
Authors:
DOOMS, Gregoire, DEVILLE, Yves, DUPONT, Pierre
Source:
Principles and practice of constraint programming - CP 2005 (11th international conference, CP 2005, Sitges, Spain, October 1-5, 2005, proceedings)Lecture notes in computer science. :211-225
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 23 ref 1
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Bioinformatique, Bioinformatics, Bioinformática, Graphe fini, Finite graph, Grafo finito, Problème combinatoire, Combinatorial problem, Problema combinatorio, Programmation logique avec contrainte, Constraint logic programming, Programación lógica con restricción, Satisfaction contrainte, Constraint satisfaction, Satisfaccion restricción, Théorie graphe, Graph theory, Teoría grafo, Graphe combinatoire
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computing Science and Engineering, Université catholique de Louvain, 1348 Louvain-la-Neuve, Belgium
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17324887
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17324887
Database:
PASCAL Archive

Further Information

In an increasing number of domains such as bioinformatics, combinatorial graph problems arise. We propose a novel way to solve these problems, mainly those that can be translated to constrained subgraph finding. Our approach extends constraint programming by introducing CP(Graph), a new computation domain focused on graphs including a new type of variable: graph domain variables as well as constraints over these variables and their propagators. These constraints are subdivided into kernel constraints and additional constraints formulated as networks of kernel constraints. For some of these constraints a dedicated global constraint and its associated propagator are sketched. CP(Graph) is integrated with finite domain and finite sets computation domains, allowing the combining of constraints of these domains with graph constraints. A prototype of CP(Graph) built over finite domains and finite sets in Oz is presented. And we show that a problem of biochemical network analysis can be very simply described and solved within CP(Graph).