Next:
Network Design
Up:
Miscellaneous
Previous:
GT50 MINIMUM TREE
-
I
NSTANCE
:
Class
C
of undirected edgecolored graphs, string
x
of colors.
-
S
OLUTION
:
A graph
and a simple path in
G
such that
the string of colors traversed in the path is equal to
x
.
-
M
EASURE
:
Cardinality of the edge set of
G
.
-
Bad News:
A
PX
-hard and not approximable within 2
for any
[
270
].
-
Comment:
The same negative results are valid also if all graphs in
C
are
caterpillars.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997