Jguirim, Wafa and Naanaa, Wady and Cooper, Martin C. Sur une classe polynomiale relationnelle pour les CSP binaires. (2015) In: 11eme Journees Francophones de Programmation par Contraintes (JFPC 2015), 22 June 2015 - 24 June 2015 (Bordeaux, France).
|
(Document in French)
PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 342kB |
Official URL: http://jfpc2015.labri.fr/downloads/actes-jfpc2015.pdf
Abstract
Trouver une solution à un probl ème de satisfaction de contraintes est en g én éral un probl ème NP-diffi cile. Ainsi, identifier une nouvelle classe polynomiale de CSP, en d'autres termes, une classe de probl èmes de satisfaction de contraintes pour lesquelles il existe une m éthode de réconnaissance et de r ésolution de complexit é polynomiale, constitue un axe de recherche fondamental dans l' étude des CSPs. Dans cet article, nous pr ésentons une nouvelle classe polynomiale relationnelle pour les CSPs binaires. Tout d'abord nous pr ésentons un nouvel op érateur ternaire que nous avons appel é mjx. Nous d écrivons ensuite les relations ferm ées par cet op érateur en proposant un algorithme d'identification de ces relations. Afin de r éduire la complexit é spatiale et temporelle des traitements, nous d éfinissons une nouvelle m éthode de stockage de ces relations qui permet de r éduire la complexit é de chemin consistance, ce dernier niveau de consistance étant suffi sant pour r ésoudre les instances de la classe propos ée.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Additional Information: | Thanks to Association française pour la Programmation par Contraintes (AFPC) editor. The definitive version is available at http://jfpc2015.labri.fr This papers appears in Actes des 11ème Journées Francophones de Programmation par Contraintes. The original PDF is available at: http://jfpc2015.labri.fr/downloads/actes-jfpc2015.pdf |
| HAL Id: | hal-01375395 |
| Audience (conference): | International conference proceedings |
| Uncontrolled Keywords: | |
| Institution: | French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (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) Other partners > Université de Monastir - UM (TUNISIA) |
| Laboratory name: | |
| Statistics: | download |
| Deposited By: | IRIT IRIT |
| Deposited On: | 13 Sep 2016 08:20 |
Repository Staff Only: item control page
