All-Pairs Almost Shortest Paths
From MaRDI portal
Recommendations
Cited in
(83)- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Localized and compact data-structure for comparability graphs
- Edge-disjoint spanners of complete graphs and complete digraphs
- All pairs shortest paths for graphs with small integer length edges
- Thorup-Zwick emulators are universally optimal hopsets
- New pairwise spanners
- Relaxed spanners for directed disk graphs
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Graph spanners: a tutorial review
- Fast approximate shortest paths in the congested clique
- Combinatorial algorithms for distributed graph coloring
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Spanners for bounded tree-length graphs
- Faster algorithms for all-pairs small stretch distances in weighted graphs
- Forming all pairs in a minimal number of steps
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- On additive spanners in weighted graphs with local error
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- All pairs lightest shortest paths
- An experimental study on approximating k shortest simple paths
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Multiplicative Approximations of Random Walk Transition Probabilities
- All-pairs shortest paths with a sublinear additive error
- Simple distributed spanners in dense congest networks
- Distance Labeling for Permutation Graphs
- Small stretch pairwise spanners and approximate D-preservers
- scientific article; zbMATH DE number 5289563 (Why is no real title available?)
- Approximating Shortest Paths in Graphs
- Sharing information for the all pairs shortest path problem
- Approximate shortest paths in weighted graphs
- Some results on approximate 1-median selection in metric spaces
- scientific article; zbMATH DE number 1043917 (Why is no real title available?)
- On the power of BFS to determine a graph's diameter
- A hierarchy of lower bounds for sublinear additive spanners
- scientific article; zbMATH DE number 6861957 (Why is no real title available?)
- An all-pairs shortest path algorithm for bipartite graphs
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Near-optimal distance emulator for planar graphs
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Time-message trade-offs in distributed algorithms
- scientific article; zbMATH DE number 7238981 (Why is no real title available?)
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Shortest-path queries in static networks
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Approximating \(k\)-spanner problems for \(k>2\)
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- STACS 2005
- Approximate distance oracles with improved preprocessing time
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- Computing almost shortest paths
- Compact roundtrip routing with topology-independent node names
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Approximate distance oracles with improved stretch for sparse graphs
- Close to linear space routing schemes
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- Improved weighted additive spanners
- All-pairs bottleneck paths in vertex weighted graphs
- New algorithms for all pairs approximate shortest paths
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Roundtrip spanners with (2k-1) stretch
- New fault tolerant subset preservers
- On the space usage of approximate distance oracles with sub-2 stretch
- New tradeoffs for decremental approximate all-pairs shortest paths
- Additive spanner lower bounds with optimal inner graph structure
- On the complexity of algorithms with predictions for dynamic graph problems
- \(f\)-sensitivity distance oracles and routing schemes
- Improved all-pairs approximate shortest paths in congested clique
- Additive sparsification of CSPs
- Approximation algorithms for directed weighted spanners
- Improved all-pairs approximate shortest paths in congested clique
- Directed buy-at-bulk spanners
- Additive, near-additive, and multiplicative approximations for APSP in weighted undirected graphs: trade-offs and algorithms
- A priority queue for the all pairs shortest path problem
- Approximate distance oracles for graphs with dense clusters
- Efficient approximation algorithms for shortest cycles in undirected graphs
This page was built for publication: All-Pairs Almost Shortest Paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4943891)
