Facebook IconTwitter IconLinkedIn IconFlickr IconYouTube IconRSS Feed Icon
 |  
sysnet • webmail • admin

Time-Dependent Shortest Paths

Friday, February 18, 11AM
POB 4.304

Subhash Suri

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