Title: Heuristics for the bandwidth colouring problem

Authors: Rafael Marti, Francisco Gortazar, Abraham Duarte

Addresses: Departamento de Estadistica e Investigacion Operativa, Facultad de Matematicas, Universitat de Valencia, Dr. Moliner 50, 46100 Burjassot, Valencia, Spain. ' Departamento de Ciencias de la Computacion, E.T.S. Ingenieria Informatica, Ed. Dept. II. C/Tulipan s/n., Universidad Rey Juan Carlos, 28933 Motoles, Madrid, Spain. ' Departamento de Ciencias de la Computacion, E.T.S. Ingenieria Informatica, Ed. Dept. II. C/Tulipan s/n., Universidad Rey Juan Carlos, 28933 Motoles, Madrid, Spain

Abstract: The bandwidth colouring problem consists of assigning a colour to each vertex of a graph, so that the absolute value of the difference between the colours of adjacent vertices is at least the value of the weight of the associated edge. This problem generalises the classical vertex colouring problem and different heuristics have recently been proposed to obtain high quality solutions. In this paper we describe both memory-based and memory-less methods to solve the bandwidth colouring problem. In particular we propose new constructive and improvement methods based on tabu search and GRASP. Comparison of our results with previously reported instances and existing heuristics indicate that the methods we propose are competitive and require short computational times. Our findings also disclose that memory appears to play a more important role during improvement phases of search than during constructive phases.

Keywords: graph colouring; tabu search; greedy randomised adaptive search procedures; GRASP; bandwidth colouring; metaheuristics; vertex colouring.

DOI: 10.1504/IJMHEUR.2010.033121

International Journal of Metaheuristics, 2010 Vol.1 No.1, pp.11 - 29

Published online: 08 May 2010 *

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