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