Next:
GT40 MINIMUM LINEAR
Up:
Vertex Ordering
Previous:
Vertex Ordering
-
I
NSTANCE
:
Graph
.
-
S
OLUTION
:
A linear ordering of
V
, i.e. a one-to-one function
.
-
M
EASURE
:
The bandwidth of the ordering, i.e.
.
-
Good News:
Approximable within
if
G
is a caterpillar [
158
].
.
Approximable within 2 if
G
is asteroidal triple-free [
235
].
-
Garey and Johnson:
GT40
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997