Next: MINIMUM CUT LINEAR ARRANGEMENT Up: Vertex Ordering Previous: MINIMUM DIRECTED BANDWIDTH Index

### MINIMUM LINEAR ARRANGEMENT

- 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 [394].

- 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 [34].

- Garey and Johnson: GT42