Tabu search for the cyclic bandwidth problem

The Cyclic Bandwidth (CB) problem for graphs consists in labeling the vertices of a guest graph G by distinct vertices of a host cycle Cn (both of order n) in such a way that the maximum distance in the cycle between adjacent vertices in G is minimized. To the best of our knowledge, this is the firs...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2015-05, Vol.57, p.17-32
Main Authors: Rodriguez-Tello, Eduardo, Romero-Monsivais, Hillel, Ramirez-Torres, Gabriel, Lardeux, Frédéric
Format: Article
Language:English
Subjects:
Algorithms
Bandwidth
Bandwidths
Best-known bounds
Combinatorial analysis
Computation
Computer Science
Cyclic bandwidth problem
Graph algorithms
Graph theory
Graphs
Heuristic
Mathematical models
Mathematical problems
Optimization algorithms
Studies
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Cyclic Bandwidth (CB) problem for graphs consists in labeling the vertices of a guest graph G by distinct vertices of a host cycle Cn (both of order n) in such a way that the maximum distance in the cycle between adjacent vertices in G is minimized. To the best of our knowledge, this is the first research work investigating the use of metaheuristic algorithms for solving this challenging combinatorial optimization problem in the case of general graphs. In this paper a new carefully devised Tabu Search algorithm, called TScb, for finding near-optimal solutions for the CB problem is proposed. Different possibilities for its key components and input parameter values were carefully analyzed and tuned, in order to find the combination of them offering the best quality solutions to the problem at a reasonable computational effort. Extensive experimentation was carried out, using 113 standard benchmark instances, for assessing its performance with respect to a Simulated Annealing (SAcb) implementation. The experimental results show that there exists a statistically significant performance amelioration achieved by TScb with respect to SAcb in 90 out of 113 graphs (79.646%). It was also found that our TScb algorithm attains 56 optimal solutions and establishes new better upper bounds for the other 57 instances. Furthermore, these competitive results were obtained expending reasonable computational times.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2014.11.013