Computing almost shortest paths
From MaRDI portal
Publication:5892152
DOI10.1145/1103963.1103968zbMath1321.05258OpenAlexW1987669032MaRDI QIDQ5892152
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Small Stretch Pairwise Spanners and Approximate $D$-Preservers, New pairwise spanners, Approximation of minimum weight spanners for sparse graphs, Some results on approximate 1-median selection in metric spaces, Faster algorithms for all-pairs small stretch distances in weighted graphs, The sparsest additive spanner via multiple weighted BFS trees, Unnamed Item, Fast deterministic distributed algorithms for sparse spanners, Simple Distributed Spanners in Dense Congest Networks, Multipath Spanners via Fault-Tolerant Spanners, Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, \(f\)-sensitivity distance oracles and routing schemes, Preprocess, set, query!, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Distributed construction of purely additive spanners, Graph spanners: a tutorial review, NP-hardness and fixed-parameter tractability of the minimum spanner problem, Approximating Shortest Paths in Graphs, Efficient distributed approximation algorithms via probabilistic tree embeddings, All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time, Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs, The Greedy Spanner Is Existentially Optimal, Fast approximation of eccentricities and distances in hyperbolic graphs, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Distributed algorithms for ultrasparse spanners and linear size skeletons, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, On Approximate Distance Labels and Routing Schemes with Affine Stretch, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, Distributed Spanner Approximation, Light spanners for high dimensional norms via stochastic decompositions, A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
