Shortest Paths in Time-varying Networks
Speaker: Kshitij Gajjar, School of Computing, National University of Singapore
Time: 5PM, 18th August, 2021
Suppose you are given the traffic situation on each road of your city and you want to find the quickest way to your workplace from your home. The city’s road network can be modelled by a graph whose edge weights represent the amount of traffic on the roads. Now the problem boils down to computing a shortest path in this graph, which can be solved by standard algorithms (Dijkstra’s algorithm, Bellman-Ford-Moore algorithm). However, in most practical scenarios, the traffic typically varies with time. So we have a graph whose edge weights are functions of time. We will see that this new setting poses some interesting mathematical questions and computational challenges, some of which have real-world implications.
Need IIIT IDs for access.