Menu
A labeling of the graph \(G\) with \(n\) vertices assigns integers \(\{1, 2, \ldots, 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.