Are there graphs whose shortest path structure requires large edge weights?
From MaRDI portal
Cites work
- A faster distributed single-source shortest paths algorithm
- A local-to-global theorem for congested shortest paths
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- A trade-off between space and efficiency for routing tables
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- An Optimal Synchronizer for the Hypercube
- Brief Announcement
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Closing the gap between directed hopsets and shortcut sets
- Decremental single-source shortest paths on undirected graphs in near-linear total update time
- Deterministic improved round-trip spanners
- Drawing Shortest Paths in Geodetic Graphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Geodesic geometry on graphs
- High-Probability Parallel Transitive-Closure Algorithms
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- scientific article; zbMATH DE number 512931 (Why is no real title available?)
- scientific article; zbMATH DE number 7788412 (Why is no real title available?)
- Irreducible nonmetrizable path systems in graphs
- Near-optimal decremental SSSP in dense weighted digraphs
- New diameter-reducing shortcuts and directed hopsets: breaking the \(O(\sqrt{n})\) barrier
- On clusterings: good, bad and spectral
- On the structure of unique shortest paths in graphs
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Preserving terminal distances using minors
- Reachability preservers: new extremal bounds and approximation algorithms
- Roundtrip spanners and roundtrip routing in directed graphs
- Roundtrip spanners with (2k-1) stretch
- Sparse Sourcewise and Pairwise Distance Preservers
- Spectral sparsification of graphs
This page was built for publication: Are there graphs whose shortest path structure requires large edge weights?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906428)
