A Heuristic Bandwidth Reduction Algorithm

Abstract

A labeling of the graph $G$ with $n$ vertices assigns integers $\{1,2,\dots ,n\}$ to the vertices of $G$. This further induces a labeling on the edges as follows: if $uv$ is an edge in $G$, then the label of $uv$ is the difference between the labels of $u$ and $v$. The $bandwidth$ of $G$ is the minimum over all possible labellings of the maximum edge label. The NP-completeness of the bandwidth problem compels the exploration of heuristic algorithms. The Gibbs-Poole-Stockmeyer algorithm (GPS) is the best-known bandwidth reduction algorithm. We introduce a heuristic algorithm that uses simulated annealing to approximate the bandwidth of a graph. We compare labellings generated by our algorithm to those obtained from GPS. Test graphs include: trees, grids, windmills, caterpillars, and random graphs. For most graphs, labellings produced by our algorithm have significantly lower bandwidth than those obtained from GPS.