Input description: A graph G=(V,E), representing an 
matrix M of
zero and nonzero elements.
Problem description: Which permutation p of the vertices of V minimizes
the length of the
longest edge when the vertices are ordered on a line, i.e. minimizes
?
Discussion: Bandwidth reduction lurks as a hidden but important problem for both
graphs and matrices, and it is important to see how it arises so as to
properly recognize it.
Applied to matrices, it permutes the rows and columns of a sparse
matrix so as to minimize the distance b of any nonzero entry from
the center diagonal.
This is important in solving linear systems, because Gaussian elimination
(see Section 
)
can be performed in 
on matrices of bandwidth b.
This is a big win over the general 
algorithm if b << n.
Bandwidth minimization on graphs arises in more subtle ways. Arranging a set of n circuit components in a line on a circuit board so as to minimize the length of the longest wire (and hence time delay) is a bandwidth problem, where each vertex of our graph corresponds to a circuit component and there is an edge for every wire linking two components. Alternatively, consider a hypertext application where we must store large objects (say images) on a magnetic tape. From each image there is a set of possible images we can go to next (i.e. the hyperlinks). To minimize the search time, we seek to place linked images near each other on the tape. This is exactly the bandwidth problem. More general formulations, such as rectangular circuit layouts and magnetic disks, inherit the same hardness and classes of heuristics from the linear versions.
Unfortunately, bandwidth minimization is NP-complete. It stays NP-complete even if the input graph is a tree whose maximum vertex degree is 3, which is an unusually strong condition. Further, there is no known approximation algorithm for bandwidth reduction, even for trees. Thus our only options are brute-force search or ad hoc heuristics.
Fortunately, ad hoc heuristics have been well-studied in the numerical analysis community, and production-quality implementations of the best heuristics are available. These are based on performing a breadth-first search from a given vertex v, where v is placed at the leftmost point of the ordering. All of the vertices that are distance 1 from v are placed to its immediate right, followed by all the vertices at distance 2, and so forth until we reach the vertex furthest from v. We then continue the breadth-first search from the vertex immediately to the right of v until all vertices in G are accounted for. The popular heuristics differ according to how many different start vertices are considered and how equidistant vertices are ordered among themselves. However, breaking ties with low-degree vertices over to the left seems to be a good idea.
Implementations of the most popular heuristics, the Cuthill-McKee and
Gibbs-Poole-Stockmeyer algorithms, are discussed in the implementation section.
The worst case of the Gibbs-Poole-Stockmeyer algorithm is ,
which would wash out any possible savings in solving linear systems,
but its performance in practice is close to linear.
Brute-force search programs can find the exact minimum bandwidth
work by backtracking through the set of n! possible permutations
of vertices.
Considerable pruning can be achieved to reduce the search space by
starting with a good heuristic bandwidth solution
and alternately adding vertices
to the left- and rightmost open slots in the partial permutation.
The first edge connecting a vertex on the left to a vertex on the right
will likely define an edge whose length is greater than our best example
to date, thus leading to fast pruning.
In our experience, graphs of size n=30 or so can be solved
to optimality.
See the discussion on backtracking in Section .
However, for almost any application such an exact solution will not
be worth the expense of finding it.
Implementations: Fortran language
implementations of both the
Cuthill-McKee algorithm [CGPS76, Gib76, CM69]
and the Gibbs-Poole-Stockmeyer algorithm [Lew82, GPS76] are
available from Netlib.
See Section .
Empirical evaluations of these and other algorithms on a test suite of
30 matrices are discussed in [Eve79b],
showing Gibbs-Poole-Stockmeyer to be the consistent winner.
Brute-force implementations written by Ingmar Bitter, Christian Joita,
and Dario Vlah in C and C++ as Stony Brook class
projects and capable of solving instances of size n=30 to optimality
are provided on the algorithm repository http://www.cs.sunysb.edu/ 
algorith.
Notes: An excellent survey on graph-theoretic and algorithmic results on the bandwidth problem to 1981 appears in [CCDG82]. Ad hoc heuristics have been widely studied, a tribute to its importance in numerical computation. Everstine [Eve79b] cites no less than 49 different bandwidth reduction algorithms!
The hardness of the bandwidth problem was first established by Papadimitriou [Pap76b], and its hardness on trees of maximum degree 3 in [GGJK78]. There are algorithms that run in polynomial time for fixed bandwidth k [Sax80]. An exposition on the hardness of the linear arrangement problem appears in [Eve79a].
Related Problems: Solving linear equations (see page ),
topological sorting (see page ).
