Graphs with Large Edge Weights for Shortest Path Structure - Sublinear Graph Simplification
Explore a structural graph problem examining the relationship between shortest paths and aspect ratio in a 32-minute lecture by Nicole Wein from the University of Michigan. Delve into the question of whether graphs with large aspect ratios can be reweighted to achieve bounded aspect ratios while maintaining their shortest path structures. Examine upper and lower bounds for this problem across undirected graphs, directed acyclic graphs (DAGs), and directed graphs. Gain insights into the implications of edge weight manipulation on graph simplification and shortest path preservation. Learn about the collaborative research conducted with Aaron Bernstein and Greg Bodwin, presented as part of the Simons Institute's "Sublinear Graph Simplification" series.