Next:
ND41 MINIMUM RECTILINEAR
Up:
Routing Problems
Previous:
ND39 LONGEST PATH
-
I
NSTANCE
:
Graph
, length function
, weight function
, specified vertices
, and integer
W
.
-
S
OLUTION
:
A simple path in
G
with total weight at most
W
, i.e., a sequence of
distinct vertices
such that, for any
,
and
.
-
M
EASURE
:
The length of the path, i.e.,
.
-
Good News:
Admits an FPTAS [
159
] and [
292
].
-
Garey and Johnson:
ND30
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997