Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes.

Résumé : De nouvelles classes traitables du CSP (Problème de Satisfaction de Contraintes) ont été récemment découvertes via l'étude de classes d'instances définies par l'exclusion de sous-problèmes décrits par des motifs. La caractérisation complète de toutes les classes traitables définies par des motifs interdits est un problème ambitieux. Nous démontrons une dichotomie dans le cas de motifs interdits constitués de deux contraintes. Ce travail nous a permis d'identifier de nouvelles classes traitables.
Type de document :
Communication dans un congrès
JFPC - Journées Francophones de Programmation par Contraintes - 2012, May 2012, Toulouse, France. 2012
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00811871
Contributeur : Guillaume Escamocher <>
Soumis le : jeudi 11 avril 2013 - 11:23:06
Dernière modification le : jeudi 11 janvier 2018 - 06:26:54
Document(s) archivé(s) le : vendredi 12 juillet 2013 - 04:05:40

Fichier

Article8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00811871, version 1

Collections

Citation

Martin Cooper, Guillaume Escamocher. Caractérisation de la complexité des classes de CSP définies par des motifs interdits à deux contraintes.. JFPC - Journées Francophones de Programmation par Contraintes - 2012, May 2012, Toulouse, France. 2012. 〈hal-00811871〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

122