Next: MINIMUM RECTILINEAR GLOBAL ROUTING Up: Routing Problems Previous: LONGEST PATH Index

### SHORTEST WEIGHT-CONSTRAINED PATH

- 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 [218] and [380].

- Garey and Johnson: ND30