Carbonnel, Clément
and Cooper, Martin C.
Tractability in constraint satisfaction problems: a survey.
(2016)
Constraints, 21 (1). 115-144. ISSN 1383-7133
|
(Document in English)
PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 266kB |
Official URL: http://dx.doi.org/10.1007/s10601-015-9198-6
Abstract
Even though the Constraint Satisfaction Problem (CSP) is NP-complete, many tractable classes of CSP instances have been identified. After discussing different forms and uses of tractability, we describe some landmark tractable classes and survey recent theoretical results. Although we concentrate on the classical CSP, we also cover its important extensions to infinite domains and optimisation, as well as #CSP and QCSP.
| Item Type: | Article |
|---|---|
| Additional Information: | Thanks to Springer editor. The original PDF can be found at: https://link.springer.com/article/10.1007/s10601-015-9198-6 |
| Audience (journal): | International peer-reviewed journal |
| Uncontrolled Keywords: | |
| Institution: | Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE) Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE) Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE) |
| Laboratory name: | |
| Statistics: | download |
| Deposited On: | 12 Sep 2017 12:00 |
Repository Staff Only: item control page
