| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [17 references]
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
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)