Computing almost shortest paths
From MaRDI portal
Publication:5892152
DOI10.1145/1103963.1103968zbMATH Open1321.05258OpenAlexW1987669032MaRDI QIDQ5892152FDOQ5892152
Authors: Michael Elkin 
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1103963.1103968
Recommendations
- Computing almost shortest paths (extended abstract)
- Efficient algorithms for constructing \((1+{\epsilon}, {\beta})\)-spanners in the distributed and streaming models
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- All-Pairs Almost Shortest Paths
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Cited In (44)
- Graph spanners: a tutorial review
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Multipath spanners via fault-tolerant spanners
- Fast deterministic distributed algorithms for sparse spanners
- Implementation of algorithms forK shortest loopless paths
- \(f\)-sensitivity distance oracles and routing schemes
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Solving shortest paths efficiently on nearly acyclic directed graphs
- Computing almost shortest paths (extended abstract)
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Preprocess, set, query!
- Shortest path solvers. From software to wetware
- Distributed spanner approximation
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Title not available (Why is that?)
- Simple distributed spanners in dense congest networks
- Point-to-Point Shortest Path Algorithms with Preprocessing
- The sparsest additive spanner via multiple weighted BFS trees
- Computing shortest paths with uncertainty
- Title not available (Why is that?)
- Calculating path algorithms
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Fast approximation of eccentricities and distances in hyperbolic graphs
- On approximate distance labels and routing schemes with affine stretch
- Approximation of minimum weight spanners for sparse graphs
- Some results on approximate 1-median selection in metric spaces
- On the equivalence between some shortest path algorithms
- Experimental and Efficient Algorithms
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- New algorithms for all pairs approximate shortest paths
- Approximating Shortest Paths in Graphs
- Title not available (Why is that?)
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- The greedy spanner is existentially optimal
- New pairwise spanners
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Small stretch pairwise spanners and approximate \(D\)-preservers
- Title not available (Why is that?)
- Shortest path with acceleration constraints: complexity and approximation algorithms
- Light spanners for high dimensional norms via stochastic decompositions
- Faster algorithms for all-pairs small stretch distances in weighted graphs
This page was built for publication: Computing almost shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892152)
