58 citations · 152 across the 7 of their papers we have counts for
6 papers · 1 filter
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…
Range and Roots: Two Common Patterns for Specifying and Propagating Counting and Occurrence Constraints
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich +2
We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We design specialised propagation algorithms for…