| Title | : | How to get from s to t, and other problems |
| Speaker | : | Kshitij Gajjar () |
| Details | : | Thu, 16 Nov, 2023 11:00 AM @ SSB-334 |
| Abstract: | : | Shortest paths in graphs have been studied in computer science for over 70 years. There are several variants of shortest path problems that have been already solved via efficient algorithms. In most real-world scenarios, the underlying graph is fixed but its edge weights are time-varying. For example, a network of roads doesn't change on a day-to-day basis but the traffic on the roads varies as a function of time. These problems are highly practical, and also find applications outside of the domain of road networks (like multi-currency arbitrage, financial investment planning). In this talk, we will embark on an introductory journey into the world of parametric shortest paths, time-dependent shortest paths and shortest path reconfiguration problems. Time permitting, we will also be discussing a voting problem, a graph labeling problem and a problem in geometric intersection graphs. |
