Next: MINIMUM CUT LINEAR ARRANGEMENT
Up: Vertex Ordering
Previous: MINIMUM DIRECTED BANDWIDTH
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A one-to-one function
].
- MEASURE:
The total length of the edges in the linear arrangement, i.e.
.
- Good News:
Approximable within
[416].
- Comment:
Admits a PTAS if
.
Variation in which the n points are on the d-dimensional grid instead of
in a line and the rectilinear metric is used also
admits a PTAS if
[36].
- Garey and Johnson: GT42
Viggo Kann
2000-03-20