Trouver une clique max dans des graphes parfaits

Un algorithme rapide pour trouver la taille de la plus grande clique dans un graphe parfait (celui-ci ayant des cycles impairs avec au moins 1 corde) avec environ 100 sommets ??Trouver une clique max dans des graphes parfaits

Et il existe une méthode plus simple que la force brute, car il s'agit d'un graphe parfait et il devrait y avoir une solution de temps polynomiale. Mais je ne suis pas capable de trouver l'algorithme.

La coloration gourmande donne-t-elle une coloration optimale dans tous les graphes parfaits?

Source

2010-06-11 copperhead

Avez-vous essayé? –

J'ai essayé quelques approches mais toutes étaient trop lentes. – copperhead

Je viens de trouver cela dans wikipedia: dans tous les graphes parfaits, le problème de coloration graphique, problème de clique maximum, et un problème de jeu indépendant maximal peuvent tous être résolus en temps polynomial (Grötschel, Lovász & Schrijver 1988) Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). Algorithmes géométriques et optimisation combinatoire. Springer-Verlag. Voir en particulier le chapitre 9, "Stable Sets in Graphs", pp. 273-303. – yogsototh

Voir page 296, avec quelques travaux, vous devriez écrire la bonne contrainte de programmation linéaire pour résoudre ce problème.

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

Source

2010-06-11 05:51:04 yogsototh

+1: Ne répondez que les adresses correspondant aux graphes parfaits, pour lesquels le problème de clique est dans P. –

100 sommets? Pffft. Brute le force en quelques secondes (peut-être une fraction de seconde) avec Cliquer. http://users.tkk.fi/pat/cliquer.html

Source

2010-06-11 06:50:49

Pouvez-vous expliquer l'algorithme (j'ai vu la documentation) mais en termes plus simples – copperhead

Bien sûr. First Cliquer définit une permutation des sommets. Je pense que par défaut c'est dans l'ordre que vous avez utilisé dans l'entrée. Deuxièmement, cliquez sur itérer pour trouver la plus grande clique de l'ensemble [i .... n], de i = n-1 à i = 1. Sur le chemin, il se souvient de la plus grande clique qu'il a trouvée jusqu'ici et lorsqu'il teste de nouvelles cliques, il élague la recherche quand il devient évident que des cliques calculées précédemment, il sera impossible que ce chemin de la recherche donne une plus grande clique. –

Trouver une clique max dans des graphes parfaits

Répondre

Questions connexes