New algorithms for all pairs approximate shortest paths
From MaRDI portal
Publication:6499232
DOI10.1145/3564246.3585197MaRDI QIDQ6499232FDOQ6499232
Authors: Liam Roditty 
Publication date: 8 May 2024
Cites Work
- Powers of tensors and fast matrix multiplication
- Approximate distance oracles
- All-Pairs Almost Shortest Paths
- Multiplying matrices faster than coppersmith-winograd
- Computing almost shortest paths
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On approximate distance labels and routing schemes with affine stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles with constant query time
- Ramsey partitions and proximity data structures
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Distance oracles beyond the Thorup-Zwick bound
- Approximate distance oracles with improved preprocessing time
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Faster Approximation of Distances in Graphs
- Space-efficient path-reporting approximate distance oracles
- An almost 2-approximation for all-pairs of shortest paths in subquadratic time
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
- Approximate distance oracles with improved bounds
- A linear-size logarithmic stretch path-reporting distance oracle for general graphs
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
- Brief announcement: A simple stretch 2 distance oracle
This page was built for publication: New algorithms for all pairs approximate shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499232)
