OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Les triangles cassés, encore et encore

Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril Les triangles cassés, encore et encore. (2016) In: 12emes Journees Francophones de Programmation par Contraintes (JFPC 2016), 15 June 2016 - 17 June 2016 (Montpellier, France).

[img]
Preview
(Document in English)

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

Official URL: https://www.supagro.fr/jfpc_jiaf_2016/actes_jfpc206.pdf

Abstract

Les triangles cassés représentent un concept important, non seulement pour la résolution en temps polynomial des problèmes de satisfaction de contraintes, mais aussi pour l'élimination de variables ou encore la réduction de la taille des domaines par la fusion des valeurs. Plus précisément, pour une variable donnée d'un CSP binaire arc-cohérent, si aucun triangle cassé ne se produit sur aucun couple de valeurs, alors cette variable peut être éliminée tout en préservant la satisfiabilité. Plus récemment, il a été démontré qu'en cas de non applicabilité de cette règle à cause de l'existence d'au moins un triangle cassé, il se peut qu'il existe deux valeurs de cette même variable sur lesquelles aucun triangle cassé ne s'est produit. Dans ce cas, ces deux valeurs peuvent être fusionnées en une seule tout en préservant la satisfiabilité. Dans ce papier, nous montrons que sous certaines conditions, et même en cas d'existence de quelques triangles cassés sur un couple de valeurs d'une variable donnée, les deux valeurs peuvent être fusionnées sans changer la satisfiabilité de l'instance.

Item Type:Conference or Workshop Item (Paper)
Additional Information:This papers appears in Actes des JFPC 2016. The original PDF is available at: https://www.supagro.fr/jfpc_jiaf_2016/actes_jfpc206.pdf
HAL Id:hal-01671343
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:11 Dec 2017 14:28

Repository Staff Only: item control page