- INSTANCE:
Directed acyclic graph
.
- SOLUTION:
A linear ordering of
*V*, i.e. a one-to-one function such that, for all ,*f(u)<f(v)*. - MEASURE:
The bandwidth of the ordering, i.e.
.

*Comment:*Approximable within 2 if every vertex has indegree [296].*Garey and Johnson:*GT41