UTCS Colloquia - Subhash Suri/University of California, Santa Barbara, "Time-Dependent Shortest Paths", ACES 4.304

Contact Name: 
Jenna Whitney
Feb 18, 2011 11:00am - 12:00pm

There is a sign-up schedule for this event that can be found at



Type of Talk: UTCS Colloquia

Speaker/Affiliation: Subhash S

uri/University of California, Santa Barbara

Talk Audience: UTCS Facul

ty and Grad Students

Date/Time: Friday, February 18, 2011, 11:00 a.


Location: ACE 4.304

Host: Subhash Suri

Talk Title: "Time-

Dependent Shortest Paths"

Talk Abstract:
In a time-dependent network

, the edge costs vary as a function of time, and therefore the shortest p

ath between two nodes can change over time. Such networks are a natural mod

el for travel time computation on road systems with time-varying congestion

. I will discuss the complexity of the arrival time function at a destinati

on over all departure times from a source. The main result shows that even

with linear edge cost functions, the arrival function exhibits super-polyn

omial complexity.

Joint work with Luca Foschini and John Hershberger [

SODA 2011]