[comp.theory] Shortest weight constrained path

kompella@beowulf.ucsd.edu (Vachaspathi Kompella) (03/07/91)

I'm looking for references to the shortest weight constrained path problem
mentioned in Garey & Johnson, section A2.3 (ND30).  G&J says that the solution
with unit weights or unit edges is poly-time computable, but gives only a
personal communication as a reference.

The problem is the following:
Given G(V, E), with two measures on each edge e,
  l(e) = length of e
  w(e) = weight of e,
  s, t vertices in V,
  K, W > 0

find the shortest path in G such that the path length is <= K, and the
path weight is <= W.  It is NP-complete, transformation from PARTITION.

Please e-mail me any references, hints to kompella@cs.ucsd.edu.  Thanks.

-Vach