We try to come up with efficient ways to remove edges from graphs without changing the shortest path distance between any two nodes by very much.

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).

Research Areas