Réordonnancement de domaines dans les réseaux de contraintes

International audienceDans le but d'accélérer la résolution d'un CSP, nous nous intéressons au problème consistant à modifier l'ordre sur les valeurs qui est induit par la définition de chaque domaine. Nous discutons de l'intérêt de cette technique de reformulation et définissons les problèmes pertinents. Nous montrons qu'on peut trouver un ordre rendant un réseau de contraintes monotone (s'il en existe un) en temps polynomial, mais que le même problème est NP-difficile pour la classe des contraintes min-closes. Enfin, nous montrons en quoi nos résultats s'appliquent au maintien de diverses consistances aux bornes