Next: MINIMUM DIRECTED BANDWIDTH
Up: Vertex Ordering
Previous: Vertex Ordering
  Index
- 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
Viggo Kann
2000-03-20