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.68036MaRDI QIDQ1001904
Sandeep Sen, Surender Baswana, Vishrut Goyal
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
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
