Les triangles cassés, encore et encore
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...