Neutrality in the Graph Coloring Problem

arXiv1301.6092MaRDI QIDQ6239034FDOQ6239034

Authors: Marie-Éléonore Marmion, Aymeric Blot, Laetitia Jourdan, Clarisse Dhaenens 

Publication date: 25 January 2013

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.

This page was built for publication: Neutrality in the Graph Coloring Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239034)