Title: Scatter search for the soft graph colouring problem

Authors: Hugo Eduardo Vásquez-Calderón; Pedro Lara-Velázquez; Sergio Gerardo De-los-Cobos-Silva; Miguel A. Gutiérrez-Andrade; Eric Alfredo Rincón-García; Roman Anselmo Mora-Gutiérrez; Antonin Ponsich

Addresses: Metropolitan Autonomous University, Iztapalapa, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, C.P. 09340, Mexico ' Electric Engineering Department, Metropolitan Autonomous University, Iztapalapa, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, C.P. 09340, Mexico ' Electric Engineering Department, Metropolitan Autonomous University, Iztapalapa, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, C.P. 09340, Mexico ' Electric Engineering Department, Metropolitan Autonomous University, Iztapalapa, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, C.P. 09340, Mexico ' Systems Department, Metropolitan Autonomous University, Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, C.P. 02200, Mexico ' Systems Department, Metropolitan Autonomous University, Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, C.P. 02200, Mexico ' Systems Department, Metropolitan Autonomous University, Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, C.P. 02200, Mexico

Abstract: The soft graph colouring problem is a model that has been used to solve problems such as scheduling under uncertainty, assignment of frequencies in the radioelectric spectrum, and pattern recognition that in certain problems can deal with risky items susceptible of error I or error II. This problem is NP-hard and requires efficient metaheuristic algorithms in order to solve it. In this paper, a scatter search algorithm is proposed and developed. This algorithm gives the best solutions in the test instances used to this day.

Keywords: scatter search; graph colouring; heuristic; optimisation.

DOI: 10.1504/IJBCRM.2018.094169

International Journal of Business Continuity and Risk Management, 2018 Vol.8 No.3, pp.200 - 218

Received: 27 Nov 2017
Accepted: 03 Apr 2018
Published online: 20 Aug 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article