Tractability in constraint satisfaction problems: a survey
2016
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
194
References
35
Citations
NaN
KQI