Authors: Matić, Dragan
Kratica, Jozef 
Filipović, Vladimir
Title: Variable neighborhood search for solving bandwidth coloring problem
Journal: Computer Science and Information Systems
Volume: 14
Issue: 2
First page: 309
Last page: 327
Issue Date: 1-Jun-2017
Rank: M23
ISSN: 1820-0214
DOI: 10.2298/CSIS160320012M
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 descent | Variable neighborhood search
Publisher: ComSIS Consortium

Show full item record


checked on May 18, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.