Skip to Main content Skip to Navigation
Conference papers

The Tractability of Global Constraints

Christian Bessière 1 Emmanuel Hébrard 2 Brahim Hnich 2 Toby Walsh 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Saturday, October 12, 2019 - 6:44:10 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Monday, January 13, 2020 - 1:43:29 PM


Files produced by the author(s)




Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Toby Walsh. The Tractability of Global Constraints. CP: Principles and Practice of Constraint Programming, Sep 2004, Toronto, Canada. pp.716-720, ⟨10.1007/978-3-540-30201-8_53⟩. ⟨lirmm-00108916⟩



Record views


Files downloads