Neutralité du problème de coloration de graphe

Résumé : Le problème de coloration de graphe (GCP) est un problème d'optimisation combinatoire très étudié dans la littérature. En effet, de nombreux problèmes réels, comme l'allocation de fréquences dans les télécommunications, sont modélisés et résolus via la coloration de graphe. Nous nous intéressons, ici, pour un nombre de couleurs donné k, à minimiser le nombre d'arêtes dont les extrémités sont identiquement coloriées. Ce nombre correspond au nombre de conflits dans la solution. De nombreuses observations font mention de la présence de solutions de même qualité, avec un nombre identique de conflits. Lorsque deux solutions voisines, en terme d'opérateur de voisinage, ont la même qualité, on parle de neutralité. Les recherches locales se déplaçant entre les solutions voisines, cette neutralité représente alors une frontière difficile à franchir. Plusieurs questions se posent alors quant à la quantité de ces solutions de même qualité et à la manière de tirer bénéfice de cette neutralité au cours de la résolution du problème. Dans cette étude, nous commencerons par quantifier et caractériser la neutralité de certaines instances difficiles de la littérature. Puis, nous montrerons que cette neutralité peut être exploitée par le processus de recherche.
Type de document :
Communication dans un congrès
ROADEF 2013 : 14e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2013, Troyes, France. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00840361
Contributeur : Marie-Eléonore Kessaci <>
Soumis le : mardi 2 juillet 2013 - 15:42:17
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 3 octobre 2013 - 04:08:51

Fichier

exemple_ROADEF2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00840361, version 1

Citation

Marie-Eleonore Marmion, Aymeric Blot, Laetitia Jourdan, Clarisse Dhaenens. Neutralité du problème de coloration de graphe. ROADEF 2013 : 14e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2013, Troyes, France. 2013. 〈hal-00840361〉

Partager

Métriques

Consultations de la notice

331

Téléchargements de fichiers

190