Recouvrement de problèmes par des hypergraphes acycliques : analyses théorique et expérimentale

Jégou Philippe 1 Samba Ndiaye 1 Cyril Terrioux 1
1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
Résumé : Cette contribution s'intéresse à la notion de recouvrement de problèmes (au sens des CSPs) par des hypergraphes acycliques (ou hyper-arbres). Elle introduit une méthode de résolution fondée sur l'exploitation d'ensemble d'hypergraphes acycliques recouvrants. Ces recouvrements peuvent être assimilés à une forme d'extension de la notion classique de décomposition arborescente de réseau de contraintes. Nous étudions ici les propriétés et les relations de ces recouvrements, puis nous évaluons leur intérêt théorique pour le cas de problèmes structurés. Nous montrons que cette approche rend possible une gestion dynamique de la structure des CSPs pendant la résolution, et facilite ainsi une exploitation aisée des heuristiques dynamiques d'ordonnancement des variables. De plus, nous proposons un résultat de complexité qui améliore significativement ceux fournis précédemment dans la littérature. Enfin, nous présentons des résultats expérimentaux qui donnent une idée de l'intérêt de cette nouvelle approche sur le plan pratique.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151228
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:33:24
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:44:58

Fichier

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

Identifiants

  • HAL Id : inria-00151228, version 1

Collections

JFPC07 | LSIS | UNIV-AMU | UNIV-TLN | LIS-LAB

Citation

Jégou Philippe, Samba Ndiaye, Cyril Terrioux. Recouvrement de problèmes par des hypergraphes acycliques : analyses théorique et expérimentale. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151228〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

116

Téléchargements de fichiers

92

Contact


archive-ouverte@inria.fr