**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 ).

Mon Jun 2 23:33:50 EDT 1997