126 citations · 298 across the 14 of their papers we have counts for
7 papers · 2 filters
Decomposition of the NVALUE constraint
Christian Bessiere, George Katsirelos, Nina Narodytska +2
We study decompositions of NVALUE, a global constraint that can be used to model a wide range of problems where values need to be counted. Whilst decomposition typically hinders pr…
Circuit Complexity and Decompositions of Global Constraints
Christian Bessiere, George Katsirelos, Nina Narodytska +1
We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive…
Decompositions of All Different, Global Cardinality and Related Constraints
Christian Bessiere, George Katsirelos, Nina Narodytska +2
We show that some common and important global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consist…
The Complexity of Reasoning with Global Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich +1
Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domain…
SLIDE: A Useful Special Case of the CARDPATH Constraint
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich +2
We study the CardPath constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CardPath where the sli…
The Parameterized Complexity of Global Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich +2
We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propaga…