- INSTANCE:
Graph
.
- SOLUTION:
A linear ordering of
*V*, i.e. a one-to-one function . - MEASURE:
The bandwidth of the ordering, i.e.
.

*Bad News:*Not approximable within 1.5 for any [81]. Not approximable with an absolute error guarantee of for every [295].*Comment:*Approximable within 3 if every vertex has degree [296]. Approximable within if*G*is a caterpillar [234]. Approximable within 2 if*G*is asteroidal triple-free [326]. Not approximable within 1.332 for any if*G*is a tree [81].*Garey and Johnson:*GT40