Approximate distance oracles with improved preprocessing time
From MaRDI portal
Publication:5743389
Recommendations
Cites work
- scientific article; zbMATH DE number 3258067 (Why is no real title available?)
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- A new approach to all-pairs shortest paths on real-weighted graphs
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- All-Pairs Almost Shortest Paths
- All-pairs small-stretch paths
- Approximate distance oracles
- Approximating Shortest Paths in Graphs
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Distance oracles beyond the Thorup-Zwick bound
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
- More algorithms for all-pairs shortest paths in weighted graphs
- New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
- Ramsey partitions and proximity data structures
- Spanners and emulators with sublinear distance errors
Cited in
(17)- Constructing Light Spanners Deterministically in Near-Linear Time
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Approximate distance oracle in \(O(n ^{2})\) time and \(O(n)\) space for chordal graphs
- scientific article; zbMATH DE number 7561542 (Why is no real title available?)
- An axiomatic approach to time-dependent shortest path oracles
- Close to linear space routing schemes
- Distance sensitivity oracles with subcubic preprocessing time and fast query time
- Approximate distance oracles with improved query time
- Improved distance sensitivity oracles with subcubic preprocessing time
- Approximate distance oracles with constant query time
- Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
- Optimal (Euclidean) Metric Compression
- New algorithms for all pairs approximate shortest paths
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Constructing light spanners deterministically in near-linear time
- Space-efficient path-reporting approximate distance oracles
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
This page was built for publication: Approximate distance oracles with improved preprocessing time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743389)