Abstract | ||
---|---|---|
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). |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11564751_18 | LECTURE NOTES IN COMPUTER SCIENCE |
Field | DocType | Volume |
Strength of a graph,Discrete mathematics,Mathematical optimization,Line graph,Graph property,Computer science,Constraint graph,Null graph,Graph (abstract data type),Voltage graph,Complement graph | Conference | 3709 |
ISSN | Citations | PageRank |
0302-9743 | 38 | 1.54 |
References | Authors | |
18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Grégoire Dooms | 1 | 65 | 5.01 |
Yves Deville | 2 | 987 | 110.84 |
Pierre Dupont | 3 | 380 | 29.30 |