Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151228
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:33:24 PM
Last modification on : Monday, March 30, 2020 - 8:53:47 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:58 PM

File

15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151228, version 1

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. ⟨inria-00151228⟩

Share

Metrics

Record views

162

Files downloads

112