Simons Institute | Are there graphs whose shortest path structure requires large edge weights? @SimonsInstituteTOC | Uploaded 1 week ago | Updated 5 minutes ago
Nicole Wein (University of Michigan)
https://simons.berkeley.edu/talks/nicole-wein-university-michigan-2024-08-02
Sublinear Graph Simplification
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
Nicole Wein (University of Michigan)
https://simons.berkeley.edu/talks/nicole-wein-university-michigan-2024-08-02
Sublinear Graph Simplification
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
