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).
|
(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.
Repository Staff Only: item control page