• 2-triangulation de micro-struc...

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

Title:
2-triangulation de micro-structure pour la résolution de CSP
Authors:
Ndiaye, Samba Ndojh
Contributors:
Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), IRISA – IETR – LTSI, Alexandre Vautier, Sylvie Saget
Source:
MajecSTIC 2005 : Manifestation des Jeunes Chercheurs francophones dans les domaines des STIC. :180-187
Publisher Information:
CCSD, 2005.
Publication Year:
2005
Collection:
collection:UNIV-TLN
collection:CNRS
collection:UNIV-AMU
collection:ENSAM
collection:MAJESTIC05
collection:LSIS
collection:LABEXIMU
collection:LIS-LAB
Subject Terms:
algorithmique des graphes, Intelligence artificielle, satisfaction de contraintes, algorithmique des graphes., [INFO.INFO-AI]Computer Science [cs], Artificial Intelligence [cs.AI]
Original Identifier:
HAL:
Document Type:
Conference conferenceObject<br />Conference papers
Language:
French
Access URL:
https://inria.hal.science/inria-00000678
https://inria.hal.science/inria-00000678v1/document
https://inria.hal.science/inria-00000678v1/file/105.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00000678v1
Database:
HAL

Further Information

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.