Many fundamental problems in computer science ask for an understanding of shortest paths in graphs (e.g. All-Pairs Shortest Paths, Radius, Diameter, many protocols in distributed networks, and so on). The time it takes for a computer to solve these problems usually depends on the size of the graph: that is, if the graph has lots of edges in it, then the algorithms will be slow. The goal of this research program is to invent ways to remove edges from graphs without changing their salient shortest path properties by too much. That way, when an algorithm is run on the smaller version of the graph, it will run much faster (in exchange for a hopefully small amount of error in the solution it produces).
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.