Skip to Main content Skip to Navigation
Conference papers

Un Algorithme de séparation et évaluation Efficace Basé sur MaxSAT pour le Problème Maxclique

Résumé : Fréquemment, L'algorithme de séparation et évaluation pour le problème Maxclique utilise une borne supérieure basée sur la partition d'un graphe en ensembles indépendants, pour obtenir la borne supérieure d'une clique maximum du graphe, qui ne peut pas être très fine pour les graphes imparfaits. Dans ce papier, nous proposons un nouveau codage de Maxclique en MaxSAT et l'utilisation de l'approche MaxSAT pour améliorer la borne supérieure basée sur la partition P. De cette manière, la puissance d'algorithmes de partitionnement d'un graphe spécifiques pour Maxclique et la performance de la méthode MaxSAT dans la logique propositionnelle sont naturellement associées pour résoudre Maxclique. Les résultats expérimentaux montrent que l'approche est très efficace sur les graphes aléatoires difficiles et sur les benchmarks Maxclique de DIMACS, et permet de fermer un problème DIMACS ouvert.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520317
Contributor : Christophe Lecoutre <>
Submitted on : Wednesday, September 22, 2010 - 7:17:08 PM
Last modification on : Tuesday, April 27, 2021 - 3:37:45 PM
Long-term archiving on: : Thursday, December 23, 2010 - 2:41:18 AM

File

quan.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : inria-00520317, version 1

Collections

Citation

Chu Min Li, Zhe Quan. Un Algorithme de séparation et évaluation Efficace Basé sur MaxSAT pour le Problème Maxclique. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.227-235. ⟨inria-00520317⟩

Share

Metrics

Record views

182

Files downloads

1486