CP(Graph) - Graph variables for constraint programming. CP(Graph)[1] defines a new computation domain in constraint programming : graph domain variables and constraints over these variables. A reference implementation of graph variables and constraints is released as a contribution package of the generic constraint development environment Gecode. The purpose of this release is to bring to the constraint community an open and reusable framework suitable for the design and implementation of graph property constraints and graph-based constraint models. The current version of the software is a first step towards a complete graph variables framework. It should be considered beta software. The graph variables are currently implemented with set variables using the ”view” concept of Gecode. One view implements a graph as a set of nodes and a set of arcs, the other view uses a set of nodes and N sets of adjacent nodes. Some constraints are also provided. The current constraints are Complement(G1,G2), Path(G,n1,n2) and Path(G,n1,n2,I,w) (see below). Constraints of monomorphism using graph variables and map variables are also provided in an other contribution (see below).

References in zbMATH (referenced in 15 articles )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Bertagnon, Alessandro: Constraint programming algorithms for route planning exploiting geometrical information (2020)
  2. Cristiá, Maximiliano; Rossi, Gianfranco: Solving quantifier-free first-order constraints over finite sets and binary relations (2020)
  3. Omrani, Mohamed Amine; Naanaa, Wady: Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs (2020)
  4. Zulkoski, Edward; Bright, Curtis; Heinle, Albert; Kotsireas, Ilias; Czarnecki, Krzysztof; Ganesh, Vijay: Combining SAT solvers with computer algebra systems to verify combinatorial conjectures (2017)
  5. Jaulin, Luc: Range-only SLAM with indistinguishable landmarks; a constraint programming approach (2016)
  6. Castaño, Fabian; Bourreau, Eric; Velasco, Nubia; Rossi, André; Sevaux, Marc: Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks (2015)
  7. Zulkoski, Edward; Ganesh, Vijay; Czarnecki, Krzysztof: MathCheck: a math assistant via a combination of computer algebra systems and SAT solvers (2015)
  8. Zampelli, Stéphane; Deville, Yves; Solnon, Christine: Solving subgraph isomorphism problems with constraint programming (2010)
  9. Viegas, Ruben Duarte; Azevedo, Francisco: Lazy constraint imposing for improving the path constraint (2009)
  10. Beldiceanu, Nicolas; Flener, Pierre; Lorca, Xavier: Combining tree partitioning, precedence, and incomparability constraints (2008)
  11. Deville, Yves; Dooms, Grégoire; Zampelli, Stéphane: Combining two structured domains for modeling various graph matching problems (2008)
  12. Vismara, Philippe; Valery, Benoît: Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms (2008)
  13. Beldiceanu, Nicolas; Carlsson, Mats; Demassey, Sophie; Petit, Thierry: Global constraint catalogue: past, present and future (2007)
  14. Beldiceanu, Nicolas; Petit, Thierry; Rochart, Guillaume: Bounds of graph parameters for global constraints (2006)
  15. Dooms, Gregoire; Deville, Yves; Dupont, Pierre: CP(Graph): Introducing a graph computation domain in constraint programming (2005)