MINIMUM LINEAR ARRANGEMENT

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

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A one-to-one function $f:V\rightarrow[1..\vert V\vert$ ].
MEASURE: The total length of the edges in the linear arrangement, i.e. $\sum_{\{u,b\}\in E}\vert f(u)-f(v)\vert$ .
Good News: Approximable within $O(\log \vert V\vert)$ [416].
Comment: Admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ . 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 $\vert E\vert =\Theta(\vert V\vert^2)$ [36].
Garey and Johnson: GT42

Viggo Kann
2000-03-20