GT40 MINIMUM LINEAR ARRANGEMENT

Next: GT41 MINIMUM CUT Up: Vertex Ordering Previous: GT39 MINIMUM BANDWIDTH

I NSTANCE : Graph .
S OLUTION : A one-to-one function .
M EASURE : The total length of the edges in the linear arrangement, i.e. .
Good News: Approximable within [ 248 ].
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 [ 23 ].
Garey and Johnson: GT42

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997