Premium
The bandwidth problem for graphs and matrices—a survey
Author(s) -
Chinn P. Z.,
Chvátalová J.,
Dewdney A. K.,
Gibbs N. E.
Publication year - 1982
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190060302
Subject(s) - combinatorics , mathematics , bandwidth (computing) , discrete mathematics , computer science , telecommunications
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.