Graph spanners: a tutorial review
From MaRDI portal
Publication:2026289
DOI10.1016/j.cosrev.2020.100253zbMath1478.68206arXiv1909.03152OpenAlexW3032246104MaRDI QIDQ2026289
Keaton Hamm, Reyan Ahmed, Greg Bodwin, Richard Spence, Faryad Darabi Sahneh, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov
Publication date: 19 May 2021
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.03152
Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items (17)
Minimum \(t\)-spanners on subcubic graphs ⋮ Parameterized complexity of directed spanner problems ⋮ On additive spanners in weighted graphs with local error ⋮ Spanners in randomly weighted graphs: Euclidean case ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ Blackout-tolerant temporal spanners ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Blackout-tolerant temporal spanners ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Multi-priority graph sparsification ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ A note on distance-preserving graph sparsification ⋮ Spanners in randomly weighted graphs: independent edge lengths ⋮ Bounded degree spanners of the hypercube ⋮ Light spanners for high dimensional norms via stochastic decompositions
Uses Software
Cites Work
- Light Spanners
- Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
- Approximate distance oracles
- Efficient distributed source detection with limited bandwidth
- Shortest-path queries in static networks
- Towards tight approximation bounds for graph diameter and eccentricities
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- On the Structure of Unique Shortest Paths in Graphs
- Greedy spanners are optimal in doubling metrics
- Additive graph spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Small Stretch Spanners on Dynamic Graphs
- Small Stretch Pairwise Spanners
- The Greedy Spanner is Existentially Optimal
- Fault Tolerant Spanners for General Graphs
- Directed spanners via flow-based linear programs
- Dynamic Algorithms for Graph Spanners
- Spanners with Slack
- Algorithms – ESA 2004
- Sparse Distance Preservers and Additive Spanners
- Automata, Languages and Programming
- New Additive Spanners
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Computing almost shortest paths
- Distributed construction of purely additive spanners
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstructing the shape of a tree from observed dissimilarity data
- On resilient graph spanners
- Approximating \(k\)-spanner problems for \(k>2\)
- Concurrent counting is harder than queuing
- Spanners in sparse graphs
- Sur la trialité et certains groupes qui s'en déduisent
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On sparse spanners of weighted graphs
- NP-completeness of minimum spanner problems
- Thorup-Zwick emulators are universally optimal hopsets
- Vertex fault tolerant additive spanners
- New pairwise spanners
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- There are planar graphs almost as good as the complete graph
- Approximation algorithms for spanner problems and directed Steiner forest
- The sparsest additive spanner via multiple weighted BFS trees
- Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Terminal embeddings
- Deterministic improved round-trip spanners
- The hardness of approximating spanner problems
- On graph problems in a semi-streaming model
- Source-wise round-trip spanners
- Dual Failure Resilient BFS Structure
- Sparse Fault-Tolerant BFS Trees
- On the locality of distributed sparse spanner construction
- Fault-tolerant spanners
- Spanners and sparsifiers in dynamic streams
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- New Doubling Spanners: Better and Simpler
- On Pairwise Spanners
- Improved Approximation for the Directed Spanner Problem
- COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
- Optimal Euclidean Spanners
- Additive Spanners: A Simple Construction
- Additive spanners and (α, β)-spanners
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Fully dynamic randomized algorithms for graph spanners
- Sparse Sourcewise and Pairwise Distance Preservers
- Geometric Spanner Networks
- Improved Purely Additive Fault-Tolerant Spanners
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Spanners and emulators with sublinear distance errors
- Additive Spanners in Nearly Quadratic Time
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Complexity of network synchronization
- Graph spanners
- Generating Low-Degree 2-Spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Generating Sparse 2-Spanners
- Computing Visibility Information in an Inaccurate Simple Polygon
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Distributed Computing: A Locality-Sensitive Approach
- Near-Optimal Light Spanners
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Approximating Low-Stretch Spanners
- Error Amplification for Pairwise Spanner Lower Bounds
- Better Distance Preservers and Additive Spanners
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- Linear Size Distance Preservers
- Ramsey Spanning Trees and Their Applications
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
- The 4/3 Additive Spanner Exponent Is Tight
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- All-Pairs Almost Shortest Paths
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- Fast Constructions of Lightweight Spanners for General Graphs
- Approximate distance oracles for geometric spanners
- Multiple Source Dual Fault Tolerant BFS Trees
- Distance-Preserving Subgraphs of Interval Graphs
- Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
- A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
- Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
- New (α, β) Spanners and Hopsets
This page was built for publication: Graph spanners: a tutorial review
