All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
From MaRDI portal
Publication:1001904
DOI10.1016/j.tcs.2008.10.018zbMath1161.68036OpenAlexW2060877994MaRDI QIDQ1001904
Vishrut Goyal, Sandeep Sen, Surender Baswana
Publication date: 19 February 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.018
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- On the exponent of all pairs shortest path problem
- Subcubic cost algorithms for the all pairs shortest path problem
- A new approach to all-pairs shortest paths on real-weighted graphs
- Gaussian elimination is not optimal
- All-Pairs Small-Stretch Paths
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Approximate distance oracles
- More algorithms for all-pairs shortest paths in weighted graphs
- Faster Approximation of Distances in Graphs
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- All-Pairs Almost Shortest Paths
- Automata, Languages and Programming
- Computing almost shortest paths
This page was built for publication: All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
