Approximate distance oracles with improved preprocessing time
From MaRDI portal
Publication:5743389
zbMATH Open1422.68197arXiv1109.4156MaRDI QIDQ5743389FDOQ5743389
Authors: Christian Wulff-Nilsen 
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1109.4156
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Approximate distance oracles
- Approximating Shortest Paths in Graphs
- All-Pairs Almost Shortest Paths
- A new approach to all-pairs shortest paths on real-weighted graphs
- More algorithms for all-pairs shortest paths in weighted graphs
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Automata, Languages and Programming
- Ramsey partitions and proximity data structures
- Distance oracles beyond the Thorup-Zwick bound
- Title not available (Why is that?)
- All-pairs small-stretch paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Spanners and emulators with sublinear distance errors
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
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
- Title not available (Why is that?)
- Close to linear space routing schemes
- An axiomatic approach to time-dependent shortest path oracles
- Distance sensitivity oracles with subcubic preprocessing time and fast query time
- Approximate distance oracles with improved query time
- Approximate distance oracles with constant query time
- Improved distance sensitivity oracles with subcubic preprocessing 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)
