Time-Dependent Shortest Paths
Friday, February 18, 11AM
In a time-dependent network, the edge costs vary as a function of time, and therefore the shortest path between two nodes can change over time. Such networks are a natural model for travel time computation on road systems with time-varying congestion. I will discuss the complexity of the arrival time function at a destination over all departure times from a source. The main result shows that even with linear edge cost functions, the arrival function exhibits super-polynomial complexity.
Joint work with Luca Foschini and John Hershberger [SODA 2011]
Host: C. Bajaj