Graph Bandwidth

In graph theory, the bandwidth of a graph is the minimum, over all ways of labeling its n vertices with distinct integers, of the maximum difference between the labels of any two adjacent vertices. This linear arrangement problem has a natural weighted variant, in which the cost of each edge is its weight multiplied by the distance between its endpoints' labels. Computing the bandwidth of a graph is NP-hard, and even approximating it within any constant factor remains NP-hard for some restricted graph families such as caterpillar trees, though heuristic methods such as the Cuthill-McKee algorithm are used in practice.