- Series
- Graph Theory Seminar
- Time
- Tuesday, September 26, 2023 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Clough Commons room 102
- Speaker
- Jan Van Den Brand – Georgia Tech – vdbrand@gatech.edu – https://faculty.cc.gatech.edu/~vdbrand/
- Organizer
- Tom Kelly
The dynamic shortest path problem seeks to maintain the shortest paths/distances between pairs of vertices in a graph that is subject to edge insertions, deletions, or weight changes. The aim is to maintain that information more efficiently than naive recomputation via, e.g., Dijkstra's algorithm.
We present the first fully dynamic algorithm maintaining exact single source distances in unweighted graphs. This resolves open problems stated in [Demetrescu and Italiano, STOC'03], [Thorup SWAT'04], [Sankowski, COCOON 2005] and [vdBrand and Nanongkai, FOCS 2019].
In this talk, we will see how ideas from fine-grained complexity theory, computer algebra, and graph theory lead to insights for dynamic shortest paths problems.