Graph bandwidth

In graph theory, the graph bandwidth problem is stated as follows. For a graph G it is to label its n vertices v_i with distinct integers f(_i) so that the quantity $\max {|f(v_{i})-f(v_{j})|}$ is minimized.

The problem may be visualized as placing the vertices of a graph into the integer points along the X-axis so that the lenggth of the longest edge is minimized.

The weighted graph bandwidth problem is a generalization whereby the edges are assigned with weights v_i

Computational complexity

The weighted versionis the special case of the quadratic bottleneck assignment problem.

The problem is NP-hard even for some special cases.