Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?
Aaron BernsteinGreg BodwinNicole WeinPublished in: ITCS (2024)
Keyphrases
- shortest path
- edge weights
- weighted graph
- minimum spanning tree
- bipartite graph
- graph structure
- finding the shortest path
- directed graph
- strongly connected components
- spanning tree
- shortest path algorithm
- flow graph
- road network
- graph partitioning
- geodesic distance
- path length
- travel time
- triangle inequality
- superpixels
- random walk