Title: Classic colouring problems as special cases of the soft graph colouring model

Authors: Daniel E. Urueta-Hinojosa; Pedro Lara-Velázquez; Miguel A. Gutiérrez-Andrade; Sergio G. De-los-Cobos-Silva; Eric A. Rincón-García; Román A. Mora-Gutiérrez; Antonin Ponsich

Addresses: Universidad Autónoma Metropolitana-Iztapalapa, Posgrado en Ciencias y Tecnologías de la Información, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340, México ' Universidad Autónoma Metropolitana-Iztapalapa, Departamento de Ingeniería Eléctrica, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340, México ' Universidad Autónoma Metropolitana-Iztapalapa, Departamento de Ingeniería Eléctrica, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340, México ' Universidad Autónoma Metropolitana-Iztapalapa, Departamento de Ingeniería Eléctrica, Av. San Rafael Atlixco 186, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340, México ' Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, México D.F., C.P. 02200, México ' Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, México D.F., C.P. 02200, México ' Universidad Autónoma Metropolitana-Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Colonia Reynosa Tamaulipas, México D.F., C.P. 02200, México

Abstract: Colouring problems can model different problems in the real world. Among the problems of colouring we have the Soft Graph Colouring, in which, given an undirected complete graph with weights on its edges (penalisations), we search to reduce the sum of the penalisations between two vertices painted with the same colour. Also, we have the classic colouring problems, which includes: minimal, weak, equitable and robust colouring. The objective of this work is to develop an integrative model that solves the classic colouring problems through the Soft Graph Colouring model and GRASP metaheuristic algorithm, using particular instances to each colouring problem that allow to compare how efficient the proposed model is; so will be possible to observe the behaviour of Soft Graph Colouring solving other types of colouring problems.

Keywords: soft graph colouring; classic colouring problems; metaheuristics; GRASP.

DOI: 10.1504/IJTPM.2019.100604

International Journal of Technology, Policy and Management, 2019 Vol.19 No.2, pp.131 - 148

Received: 30 Sep 2017
Accepted: 14 May 2018
Published online: 05 Jul 2019 *

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