Theory Seminar

Are there graphs whose shortest path structure requires large edge weights?

Nicole WeinSimons Institute
WHERE:
3941 Beyster BuildingMap
SHARE:
I will discuss a new structural graph problem that investigates the relationship between the shortest paths in a graph and the aspect ratio (the ratio of the largest to smallest edge weight in the graph). The question is: can one take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths? I will present upper and lower bounds for this question for undirected graphs, DAGs, and directed graphs.
Joint work with Aaron Bernstein and Greg Bodwin

Organizer

Greg Bodwin

Organizer

Euiwoong Lee