OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Une famille de classes polynomiales de CSP bas ée sur la microstructure

Cooper, Martin C. and Jégou, Philippe and Terrioux, Cyril Une famille de classes polynomiales de CSP bas ée sur la microstructure. (2015) In: 11eme Journees Francophones de Programmation par Contraintes (JFPC 2015), 22 June 2015 - 24 June 2015 (Bordeaux, France).

[img]
Preview
(Document in French)

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

Abstract

L’étude des classes polynomiales constitue une question importante en intelligence artificielle, en particulier au niveau des problèmes de satisfaction de contraintes. Dans ce contexte, la propriété BTP fournit une classe importante de l’état de l’art. Dans cet article, nous proposons d’étendre et de généraliser cette classe en introduisant la propriété k-BTP (et la classe des instances satisfaisant cette propriété) où le paramètre k est une constante donnée. Ainsi, nous avons 2-BTP = BTP, et pour k > 2, k-BTP est une relaxation de BTP au sens où k-BTP ( (k + 1)-BTP. En outre, nous montrons que si k-TW est la classe d’instances ayant une largeur arborescente bornée par une constante k, alors k-TW ((k+1)-BTP. Au niveau de la complexité, nous montrons que les instances satisfaisant k-BTP et qui vérifient la k-cohérence-forte sont reconnaissables et résolubles en temps polynomial. Nous étudions aussi la relation entre k-BTP et l’approche de W. Naanaa qui a proposé un outil théorique connu sous le vocable directional rank afin d’´étendre les classes polynomiales de manière paramétrée. Enfin, nous proposons une étude expérimentale de 3-BTP qui montre l’intérêt pratique de cette classe.

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-01375398
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Other partners > Aix-Marseille Université - AMU (FRANCE)
Other partners > Arts et Métiers ParisTech (FRANCE)
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 Toulon - UTLN (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:13 Sep 2016 10:00

Repository Staff Only: item control page