Neutrality in the Graph Coloring Problem

Abstract : The graph coloring problem is often investigated in the literature. Many insights about many neighboring solutions with the same fitness value are raised but as far as we know, no deep analysis of this neutrality has ever been conducted in the literature. In this paper, we quantify the neutrality of some hard instances of the graph coloring problem. This neutrality property has to be detected as it impacts the search process. Indeed, local optima may belong to plateaus that represents a barrier for local search methods. In this work, we also aim at pointing out the interest of exploiting neutrality during the search. Therefore, a generic local search dedicated to neutral problems, NILS, is performed on several hard instances.
Type de document :
[Research Report] RR-8215, INRIA. 2013, pp.15
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
Contributeur : Laetitia Jourdan <>
Soumis le : vendredi 25 janvier 2013 - 14:39:31
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 26 avril 2013 - 03:55:35


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00781001, version 1
  • ARXIV : 1301.6092


Marie-Eleonore Marmion, Aymeric Blot, Laetitia Jourdan, Clarisse Dhaenens. Neutrality in the Graph Coloring Problem. [Research Report] RR-8215, INRIA. 2013, pp.15. 〈hal-00781001〉



Consultations de la notice


Téléchargements de fichiers