Geodesic
Variable Neighborhood Search for solving Bandwidth Coloring Problem
Computer Science and Information Systems, Tome 14 (2017) no. 2.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

This paper presents a variable neighborhood search (VNS) algorithm for solving bandwidth coloring problem (BCP) and bandwidth multicoloring problem (BMCP). BCP and BMCP are generalizations of the well known vertex coloring problem and they are of a great interest from both theoretical and practical points of view. Presented VNS combines a shaking procedure which perturbs the colors for an increasing number of vertices and a specific variable neighborhood descent (VND) procedure, based on the specially designed arrangement of the vertices which are the subject of re-coloring. By this approach, local search is split in a series of disjoint procedures, enabling better choice of the vertices which are addressed to recolor. The experiments performed on the geometric graphs from the literature show that proposed method is highly competitive with the state-of-the-art algorithms and improves 2 out of 33 previous best known solutions for BMCP.
Keywords: Bandwidth Coloring, Bandwidth MultiColoring, Frequency Assignment, Variable Neighborhood Search, Variable Neighborhood Descent 
@article{CSIS_2017_14_2_a2,
     author = {Dragan Mati\'c and Jozef Kratica and Vladimir Filipovi\'c},
     title = {Variable {Neighborhood} {Search} for solving {Bandwidth} {Coloring} {Problem}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2017},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2017_14_2_a2/}
}
TY  - JOUR
AU  - Dragan Matić
AU  - Jozef Kratica
AU  - Vladimir Filipović
TI  - Variable Neighborhood Search for solving Bandwidth Coloring Problem
JO  - Computer Science and Information Systems
PY  - 2017
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2017_14_2_a2/
ID  - CSIS_2017_14_2_a2
ER  - 
%0 Journal Article
%A Dragan Matić
%A Jozef Kratica
%A Vladimir Filipović
%T Variable Neighborhood Search for solving Bandwidth Coloring Problem
%J Computer Science and Information Systems
%D 2017
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2017_14_2_a2/
%F CSIS_2017_14_2_a2
Dragan Matić; Jozef Kratica; Vladimir Filipović. Variable Neighborhood Search for solving Bandwidth Coloring Problem. Computer Science and Information Systems, Tome 14 (2017) no. 2. http://geodesic.mathdoc.fr/item/CSIS_2017_14_2_a2/