OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A polynomial relational class of binary CSP

Jguirim, Wafa and Naanaa, Wady and Cooper, Martin C. A polynomial relational class of binary CSP. (2018) Annals of Mathematics and Artificial Intelligence, 83 (1). 1-20. ISSN 1012-2443

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
410kB

Official URL: https://doi.org/10.1007/s10472-017-9566-6

Abstract

Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP,in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism).

Item Type:Article
HAL Id:hal-02640862
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (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)
Other partners > Université de Monastir - UM (TUNISIA)
Laboratory name:
Statistics:download
Deposited On:05 May 2020 14:06

Repository Staff Only: item control page