Skip to Main content Skip to Navigation
Conference papers

2-triangulation de micro-structure pour la résolution de CSP

Résumé : Un CSP ou problème de satisfaction de contraintes, consiste à donner des valeurs à des variables en respectant les contraintes qui les lient. Mais le problème de décision associé à un CSP est NP-complet. Dans [Jégou, 1993], Jégou propose une méthode, basée sur la décomposition de la micro-structure du CSP et dans [Chmeiss, 2003], une généralisation de cette méthode est présentée en utilisant une généralisation des graphes triangulés : les graphes CSGk. Nous proposons une amélioration de la décomposition de CSP basée sur les graphes CSG2. Cela passe par un calcul de 2-triangulation plus efficace tant au niveau de la complexité qu'à celui de la qualité de la décomposition, mais aussi un algorithme de recherche de cliques maximales dans les graphes 2-triangulés, apportant de bons résultats en pratique.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00000678
Contributor : Anne Jaigu <>
Submitted on : Monday, November 14, 2005 - 3:28:10 PM
Last modification on : Monday, March 30, 2020 - 8:52:52 AM
Document(s) archivé(s) le : Friday, April 2, 2010 - 7:09:09 PM

File

Identifiers

  • HAL Id : inria-00000678, version 1

Citation

Samba Ndojh Ndiaye. 2-triangulation de micro-structure pour la résolution de CSP. MajecSTIC 2005 : Manifestation des Jeunes Chercheurs francophones dans les domaines des STIC, IRISA – IETR – LTSI, Nov 2005, Rennes, pp.180-187. ⟨inria-00000678⟩

Share

Metrics

Record views

170

Files downloads

116