Skip to Main content Skip to Navigation
Conference papers

HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking

Résumé : L'hypertree decomposition généralisée est l'approche la plus générale connue dans la littérature pour identifier des sous classes traitables de problèmes de satisfaction de contraintes (CSPs) n-aires représentés à l'aide d'hypergraphes. Seulement, quoi que sa complexité théorique est bornée par la largeur de la décomposition, la méthode proposée pour la résolution du CSP donné sous forme d'hypertree n'est pas efficace en pratique. Dans ce papier, nous proposons la méthode HD DBT (pour résolution des CSP par un algorithme de type BT sur les tuples guidé par un ordre statique induit par une Hypertree Décomposition) comme une nouvelle approche de résolution des CSPs préalablement décomposés en hypertree généralisée. Nous avons implémenté et expérimenté cette approche. Les résultats de comparaison par rapport à la méthode de résolution des CSPs par hypertree decomposition, connue dans la littérature sont encourageants.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00519487
Contributor : Christophe Lecoutre Connect in order to contact the contributor
Submitted on : Monday, September 20, 2010 - 2:46:03 PM
Last modification on : Wednesday, May 18, 2016 - 1:01:20 AM
Long-term archiving on: : Tuesday, December 21, 2010 - 3:00:06 AM

File

amroun.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : inria-00519487, version 1

Collections

Citation

Kamal Amroun, Zineb Habbas. HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.5-12. ⟨inria-00519487⟩

Share

Metrics

Record views

74

Files downloads

86