 |
HAL-LIRMM - Open Archive |  |
Conference papers
The Tractability of Global Constraints
Abstract : Constraint propagation is one of the techniques central to the success of constraint programming. Fast algorithms are used to prune the search space either before or during backtracking search. Propagating global constraints is intractable in general. In this paper, we characterize a number of important questions related to constraint propagation. For example, we consider the two questions: "Is this problem generalized arc-consistent?" and "What are the maximal generalized arc-consistent domains?". We identify dependencies between the tractability and intractability of these questions for finite domain variables. Finally, we prove intractability for a range of global constraints.
Cited literature [8 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108916
Contributor : Christine Carvalho de Matos <>
Submitted on : Saturday, October 12, 2019 - 6:44:10 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM
Long-term archiving on: : Monday, January 13, 2020 - 1:43:29 PM
Contributor : Christine Carvalho de Matos <>
Submitted on : Saturday, October 12, 2019 - 6:44:10 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM
Long-term archiving on: : Monday, January 13, 2020 - 1:43:29 PM
File
cp04-tractability.pdf
Files produced by the author(s)