Unifying and extending hybrid tractable classes of CSPs
Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-complete task. Many works have been concerned with identifying tractable classes of CSPs. Tractability is obtained by imposing specific problem structures, specific constraint relations or both. A tractable CSP class whose tractability is due to both structural and relational properties is said to be hybrid. In this article, we present a hybrid tractable CSP class that brings together and generalises many known hybrid tractable CSPs. The proposed class is characterised by means of simple but powerful notions from set theory.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
Document Type: Research Article
Affiliations: Department of Computer Science, Faculty of Sciences, University of Monastir, Monastir 5000, Tunisia
Publication date: December 1, 2013