The bandwidth problem for graphs and matrices—a survey

The bandwidth problem for a graph G is to label its n vertices v_i with distinct integers f(v_i) so that the quantity max{| f(v_i) ? f(v_i)| : (v_i v_j) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i ? j| : m'_ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.