Neutrality in the Graph Coloring Problem

Abstract : In this paper, the neutrality of some hard instances of the graph coloring problem (GCP) is quantified. This neutrality property has to be detected as it impacts the search process. Indeed, local optima may belong to plateaus that represent a barrier for local search methods. Then, 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 :
Communication dans un congrès
Pardalos, Panos and Nicosia, Giuseppe. Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. LNCS (Springer), pp.125--130, 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00919750
Contributeur : Marie-Eléonore Kessaci <>
Soumis le : mardi 17 décembre 2013 - 11:45:03
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : hal-00919750, version 1

Citation

Marie-Eleonore Marmion, Aymeric Blot, Laetitia Jourdan, Clarisse Dhaenens. Neutrality in the Graph Coloring Problem. Pardalos, Panos and Nicosia, Giuseppe. Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. LNCS (Springer), pp.125--130, 2013. 〈hal-00919750〉

Partager

Métriques

Consultations de la notice

187