OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Autour des Triangles Cassés

Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril and Zanuttini, Bruno Autour des Triangles Cassés. (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
133kB

Official URL: http://jfpc2015.labri.fr/downloads/actes-jfpc2015.pdf

Abstract

Une instance CSP binaire qui satisfait la propriété des triangles cassés (BTP) peut être résolue en temps polynomial. Malheureusement, en pratique, peu d'instances satisfont cette propriété. Nous montrons qu'une version locale de BTP permet de fusionner des valeurs dans les domaines d'instances binaires quelconques. Des expérimentations sur des instances benchmarks démontrent la diminution significative de la taille de l'instance pour certaines classes de problèmes. Nous montrons que cette fusion peut être gén éralisée aux instances ayant des contraintes d'arité quelconque et nous étudions les liens avec la résolution dans SAT. Une version orientée nous permet ensuite d'étendre la classe polynomiale BTP précédemment définie pour les CSP binaires. Ce papier est un résume de l'article M. C. Cooper, A. El Mouelhi, C. Terrioux et B. Zanuttini. On Broken Triangle In Proceedings of CP, LNCS 8656, 9-24, 2014.

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
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)
Other partners > Ecole Nationale Supérieure d'Ingénieurs de Caen - ENSICAEN (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 Caen Basse-Normandie (FRANCE)
Other partners > Université de Toulon - UTLN (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:13 Sep 2016 10:03

Repository Staff Only: item control page