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.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.227-235, 2010
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520317
Contributeur : Christophe Lecoutre <>
Soumis le : mercredi 22 septembre 2010 - 19:17:08
Dernière modification le : jeudi 23 septembre 2010 - 10:50:41
Document(s) archivé(s) le : jeudi 23 décembre 2010 - 02:41:18

Fichier

quan.pdf
Accord explicite pour ce dépôt

Identifiants

  • 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, 2010. 〈inria-00520317〉

Partager

Métriques

Consultations de la notice

156

Téléchargements de fichiers

837