Iterated Local Search with Tabu Search for the Bandwidth Reduction Problem in Graphs

This paper addresses the bandwidth reduction problem in graphs, which is relevant in several applications, such as reducing memory consumption and computational cost in solving systems of linear equations. This problem consists of renumbering the vertices of a graph so that the difference between the labels of adjacent vertices is as low as possible. This paper shows a novel hybrid method based on the Iterated Local Search and Tabu Search (ILSTS) metaheuristics. The paper conducted the experiments using several graphs from the SuiteSparse Matrix Collection and compared the results with the current state-of-the-art Dual Representation Simulated Annealing (DRSA). The obtained results highlight that, although ILSTS demonstrates promising outcomes in terms of bandwidth reduction while maintaining low computational cost, it does not achieve competitive results compared to the quality of the solution delivered by DRSA.