Lower Bounds for the Bandwidth Problem

DOI10.1016/J.COR.2021.105422MaRDI QIDQ6317165arXivFDO

Authors Franz Rendl, Renata Sotirov, Christian Truden

Publication date 14 April 2019

Full work available at URL https://doi.org/10.1016/J.COR.2021.105422

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Programming involving graphs or networks (90C35)

arXiv classification

math.OC

Abstract: The Bandwidth Problem seeks for a simultaneous permutation of the rows and columns of the adjacency matrix of a graph such that all nonzero entries are as close as possible to the main diagonal. This work focuses on investigating novel approaches to obtain lower bounds for the bandwidth problem. In particular, we use vertex partitions to bound the bandwidth of a graph. Our approach contains prior approaches for bounding the bandwidth as special cases. By varying sizes of partitions, we achieve a trade-off between quality of bounds and efficiency of computing them. To compute lower bounds, we derive a Semidefinite Programming relaxation. We evaluate the performance of our approach on several data sets, including real-world instances.

This page was built for publication: Lower Bounds for the Bandwidth Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317165)