Speaker

Greg Bodwin, assistant professor, Computer Science, University of Michigan

Abstract

A shortest path between two nodes in a graph is a route between them of minimum length.  Computing, storing, and retrieving shortest paths are basic algorithmic problems in computer science.  But what distinguishes these problems from the corresponding questions about non-shortest paths?  In other words, what mathematical properties of shortest paths can be leveraged to solve them more efficiently?

We will survey a handful of influential structure theorems about shortest paths that have been discovered throughout the years, including applications in computer science, modern continuations of these lines of thought, and some outstanding open problems.  No prior knowledge is assumed.

Bio

Greg Bodwin is an assistant professor of computer science at the University of Michigan, and currently holds the Morris Wellman faculty development professorship.  He received his Ph.D. from MIT in 2018.  His research is on algorithms for graph sparsification, especially as related to shortest paths, distances, or reachability.