OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Tractability in constraint satisfaction problems: a survey

Carbonnel, Clément and Cooper, Martin C. Tractability in constraint satisfaction problems: a survey. (2016) Constraints, 21 (1). 115-144. ISSN 1383-7133

[img]
Preview
(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 - INPT (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (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 By: IRIT IRIT
Deposited On:12 Sep 2017 12:00

Repository Staff Only: item control page