Computing almost shortest paths
From MaRDI portal
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
Cited in
(49)- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Calculating path algorithms
- New pairwise spanners
- Shortest path solvers. From software to wetware
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Preprocess, set, query!
- Graph spanners: a tutorial review
- Shortest path with acceleration constraints: complexity and approximation algorithms
- Light spanners for high dimensional norms via stochastic decompositions
- The sparsest additive spanner via multiple weighted BFS trees
- Faster algorithms for all-pairs small stretch distances in weighted graphs
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- On the equivalence between some shortest path algorithms
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- On approximate distance labels and routing schemes with affine stretch
- scientific article; zbMATH DE number 434492 (Why is no real title available?)
- Simple distributed spanners in dense congest networks
- Computing shortest paths with uncertainty
- Small stretch pairwise spanners and approximate D-preservers
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Approximating Shortest Paths in Graphs
- Implementation of algorithms forK shortest loopless paths
- scientific article; zbMATH DE number 124663 (Why is no real title available?)
- scientific article; zbMATH DE number 176771 (Why is no real title available?)
- Some results on approximate 1-median selection in metric spaces
- Multipath spanners via fault-tolerant spanners
- The greedy spanner is existentially optimal
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Distributed spanner approximation
- Light spanners for high dimensional norms via stochastic decompositions
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Point-to-Point Shortest Path Algorithms with Preprocessing
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Experimental and Efficient Algorithms
- Computing almost shortest paths (extended abstract)
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Approximation of minimum weight spanners for sparse graphs
- New algorithms for all pairs approximate shortest paths
- A unified framework of light spanners. I: Fast (yet optimal) constructions
- \(f\)-sensitivity distance oracles and routing schemes
- On the edge crossings of the greedy spanner
- Approximation algorithms for directed weighted spanners
- Constant-round spanners and shortest paths in congested clique and MPC
- Directed buy-at-bulk spanners
- Solving shortest paths efficiently on nearly acyclic directed graphs
- Fast deterministic distributed algorithms for sparse spanners
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)
