The Tractability of Global Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2004

The Tractability of Global Constraints


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.
Fichier principal
Vignette du fichier
cp04-tractability.pdf (69.3 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00108916 , version 1 (12-10-2019)



Christian Bessiere, 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⟩
133 View
103 Download



Gmail Facebook X LinkedIn More