#### Theory Seminar

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

Nicole WeinSimons Institute

WHERE:

3941 Beyster BuildingMap

WHEN:

Tuesday, November 14, 2023 @ 2:00 pm - 3:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

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