Variable Neighborhood Search for solving Bandwidth Coloring Problem

Dragan Matić1, Jozef Kratica2 and Vladimir Filipović3

  1. Faculty of Mathematics and Natural Sciences, Mladena Stojanovića 2
    78000 Banjaluka, Bosnia and Herzegovina
    matic.dragan@gmail.com
  2. Mathematical Institute of the Serbian Academy of Sciences and Arts
    11000 Belgrade, Serbia
    jkratica@gmail.com
  3. Faculty of Mathematics, Studentski trg 16
    11000 Belgrade, Serbia
    vladofilipovic@hotmail.com

Abstract

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.

Key words

Bandwidth Coloring, Bandwidth MultiColoring, Frequency Assignment, Variable Neighborhood Search, Variable Neighborhood Descent

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS160320012M

Publication information

Volume 14, Issue 2 (June 2017)
Year of Publication: 2017
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Matić, D., Kratica, J., Filipović, V.: Variable Neighborhood Search for solving Bandwidth Coloring Problem. Computer Science and Information Systems, Vol. 14, No. 2, 309–327. (2017)