Virginia Vassilevska

Nondecreasing Paths in a Weighted Graph or:
How to Optimally Read a Train Schedule

Abstract:
A travel booking office has timetables giving arrival and departure times
for all scheduled trains, including their origins and destinations. A
customer presents a starting city and demands a route with perhaps several
train connections taking him to his destination as early as possible. The
booking office must find the best route for its customers. This problem
was first considered in the theory of algorithms in 1958 by George Minty,
who reduced it to a problem on directed edge-weighted graphs: find a path
from a given source to a given target such that the consecutive weights on
the path are nondecreasing and the last weight on the path is minimized.
Minty gave the first algorithm for the single source version of the
problem, in which one finds minimum last weight nondecreasing paths from
the source to every other vertex. In this talk we present the first linear
time algorithm for this problem. The algorithm uses some nice data
structures and is surprisingly simple and elegant.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.