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
2 LINA - Laboratoire d'Informatique de Nantes Atlantique
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.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.133-142, 2008
Liste complète des métadonnées

https://hal.inria.fr/inria-00291550
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 13:35:03
Dernière modification le : samedi 10 juin 2017 - 01:08:14
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:24:41

Fichier

pages-133-142-article45.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291550, version 1

Collections

JFPC08 | LINA-TASC | LINA | GREYC | GREYC-MAD | MINES-NANTES | INFO | COCONUT | LIRMM

Citation

Christian Bessière, Thierry Petit, Bruno Zanuttini. Réordonnancement de domaines dans les réseaux de contraintes. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.133-142, 2008. <inria-00291550>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

141

Téléchargements du document

126

Contact


archive-ouverte@inria.fr