Group for Research in Decision Analysis


Paths with Minimum Range and Ratio of Arc Lengths

, , and

Two new path problems in graphs are studied: MINRANGE, i.e., find a path from a vertex s to a vertex t with the smallest possible range of arc lengths, and MINRATIO, i.e., find such a path for which the ratio of the largest to the smallest arc length is minimum. Several bicriterion extensions of these problems are also considered.

, 20 pages

This cahier was revised in August 1996