Skip to Main content Skip to Navigation
Conference papers

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

Christian Bessière 1 Thierry Petit 2 Bruno Zanuttini 3
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

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

File

pages-133-142-article45.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291550, version 1

Citation

Christian Bessière, Thierry Petit, Bruno Zanuttini. Réordonnancement de domaines dans les réseaux de contraintes. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.133-142. ⟨inria-00291550⟩

Share

Metrics

Record views

374

Files downloads

181