Spanners and emulators with sublinear distance errors
From MaRDI portal
Cited in
(41)- Thorup-Zwick emulators are universally optimal hopsets
- New pairwise spanners
- Sublinear fully distributed partition with applications
- Preprocess, set, query!
- Graph spanners: a tutorial review
- A fast algorithm for source-wise round-trip spanners
- Sparsification lower bound for linear spanners in directed graphs
- Fast approximate shortest paths in the congested clique
- Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
- Covering metric spaces by few trees
- Demand-aware network designs of bounded degree
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Deterministic improved round-trip spanners
- Source-wise round-trip spanners
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Multiplicative Approximations of Random Walk Transition Probabilities
- On approximate distance labels and routing schemes with affine stretch
- Small stretch pairwise spanners and approximate D-preservers
- Approximating Shortest Paths in Graphs
- A hierarchy of lower bounds for sublinear additive spanners
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Near-optimal distance emulator for planar graphs
- Covering Metric Spaces by Few Trees
- Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Hopsets with constant hopbound, and applications to approximate shortest paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
- Approximate distance oracles with improved preprocessing time
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Close to linear space routing schemes
- Improved weighted additive spanners
- Almost-optimal sublinear additive spanners
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- New tradeoffs for decremental approximate all-pairs shortest paths
- On the size overhead of pairwise spanners
- Massively parallel algorithms for approximate shortest paths
- A unified framework for hopsets
- Lightweight near-additive spanners
- k-leaf powers cannot be characterized by a finite set of forbidden induced subgraphs for k 5
- New approximate distance oracles and their applications
This page was built for publication: Spanners and emulators with sublinear distance errors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581551)
