Skip to Main content Skip to Navigation
New interface
Conference papers

Neutrality in the Graph Coloring Problem

Marie-Eleonore Marmion 1, 2 Aymeric Blot 1, 2 Laetitia Jourdan 1, 2 Clarisse Dhaenens 1, 2 
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
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.
Document type :
Conference papers
Complete list of metadata
Contributor : Marie-Eléonore Kessaci Connect in order to contact the contributor
Submitted on : Tuesday, December 17, 2013 - 11:45:03 AM
Last modification on : Thursday, January 20, 2022 - 5:27:54 PM


  • HAL Id : hal-00919750, version 1


Marie-Eleonore Marmion, Aymeric Blot, Laetitia Jourdan, Clarisse Dhaenens. Neutrality in the Graph Coloring Problem. Learning and Intelligent OptimizatioN Conference, Jan 2013, Catania, Italy. pp.125--130. ⟨hal-00919750⟩



Record views