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
[75].
Not approximable with an absolute error
guarantee of
for every
[280].
- Comment:
Approximable within 3 if every vertex has degree
[281].
Approximable within
if G is a caterpillar [217].
Approximable within 2 if G is asteroidal triple-free [309].
Not approximable within 1.332
for any
if G is a tree
[75].
- Garey and Johnson: GT40
Viggo Kann
1999-04-22