Skip to Main content Skip to Navigation
Journal articles

The $k$-coloring fitness landscape

Abstract : This paper deals with the fitness landscape analysis of the $k$-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global and local structure of fitness landscapes. An approximative distance on the $k$-coloring space is proposed to perform these statistical measures. Local search operator trajectories on various landscapes are then studied using the time series analysis. Results are used to better understand the behavior of metaheuristics based on local search when dealing with the graph coloring problem.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00836736
Contributor : Talbi El-Ghazali <>
Submitted on : Friday, June 21, 2013 - 2:26:56 PM
Last modification on : Wednesday, April 28, 2021 - 11:57:56 AM

Links full text

Identifiers

Citation

Hind Bouziri, Khaled Mellouli, El-Ghazali Talbi. The $k$-coloring fitness landscape. Journal of Combinatorial Optimization, Springer Verlag, 2011, 21, pp.306-329. ⟨10.1007/s10878-009-9249-2⟩. ⟨hal-00836736⟩

Share

Metrics

Record views

339