Next: MINIMUM RECTILINEAR GLOBAL ROUTING
Up: Routing Problems
Previous: LONGEST PATH
  Index
- INSTANCE:
Graph
,
length function
,
weight function
,
specified vertices ,
and integer W.
- SOLUTION:
A simple path in G with total weight at most W, i.e., a sequence of
distinct vertices
such that, for any
,
and
.
- MEASURE:
The length of the path, i.e.,
.
- Good News:
Admits an FPTAS [235] and [402].
- Garey and Johnson: ND30
Viggo Kann
2000-03-20