| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Réordonnancement de domaines dans les réseaux de contraintes
Résumé : Dans 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.
Cited literature [15 references]
https://hal.inria.fr/inria-00291550
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 1:35:03 PM
Last modification on : Monday, January 11, 2021 - 5:24:06 PM
Long-term archiving on: : Friday, May 28, 2010 - 8:24:41 PM
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 1:35:03 PM
Last modification on : Monday, January 11, 2021 - 5:24:06 PM
Long-term archiving on: : Friday, May 28, 2010 - 8:24:41 PM
File
pages-133-142-article45.pdf
Files produced by the author(s)