Graph spanners: a tutorial review (Q2026289): Difference between revisions

@@ Property / DOI @@
-.1016/j.cosrev.2020.100253
@@ Property / DOI: 10.1016/j.cosrev.2020.100253 / rank @@
-Normal rank
@@ Property / describes a project that uses @@
+Graphs
@@ Property / describes a project that uses: Graphs / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3032246104
@@ Property / OpenAlex ID: W3032246104 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.03152
@@ Property / arXiv ID: 1909.03152 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph spanners
@@ Property / cites work: Graph spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of network synchronization
@@ Property / cites work: Complexity of network synchronization / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles for geometric spanners
+Normal rank
@@ Property / cites work @@
+Geometric Spanner Networks
@@ Property / cites work: Geometric Spanner Networks / rank @@
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Lower Bounds for Sublinear Additive Spanners
+Normal rank
@@ Property / cites work @@
+On sparse spanners of weighted graphs
@@ Property / cites work: On sparse spanners of weighted graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Generating Sparse 2-Spanners
@@ Property / cites work: Generating Sparse 2-Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+An Optimal Synchronizer for the Hypercube
@@ Property / cites work: An Optimal Synchronizer for the Hypercube / rank @@
+Normal rank
@@ Property / cites work @@
+There are planar graphs almost as good as the complete graph
+Normal rank
@@ Property / cites work @@
+Q5610919
@@ Property / cites work: Q5610919 / rank @@
+Normal rank
@@ Property / cites work @@
+Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
+Normal rank
@@ Property / cites work @@
+Q4449190
@@ Property / cites work: Q4449190 / rank @@
+Normal rank
@@ Property / cites work @@
+Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
+Normal rank
@@ Property / cites work @@
+Sur la trialité et certains groupes qui s'en déduisent
+Normal rank
@@ Property / cites work @@
+NP-completeness of minimum spanner problems
@@ Property / cites work: NP-completeness of minimum spanner problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating \(k\)-spanner problems for \(k>2\)
@@ Property / cites work: Approximating \(k\)-spanner problems for \(k>2\) / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of approximating spanner problems
@@ Property / cites work: The hardness of approximating spanner problems / rank @@
+Normal rank
@@ Property / cites work @@
+Label Cover Instances with Large Girth and the Hardness of Approximating Basic             <i>k</i>             -Spanner
+Normal rank
@@ Property / cites work @@
+Q2754183
@@ Property / cites work: Q2754183 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3836515
@@ Property / cites work: Q3836515 / rank @@
+Normal rank
@@ Property / cites work @@
+NP-hardness and fixed-parameter tractability of the minimum spanner problem
+Normal rank
@@ Property / cites work @@
+Additive graph spanners
@@ Property / cites work: Additive graph spanners / rank @@
+Normal rank
@@ Property / cites work @@
+The Greedy Spanner is Existentially Optimal
@@ Property / cites work: The Greedy Spanner is Existentially Optimal / rank @@
+Normal rank
@@ Property / cites work @@
+Additive Spanners: A Simple Construction
@@ Property / cites work: Additive Spanners: A Simple Construction / rank @@
+Normal rank
@@ Property / cites work @@
+A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Greedy spanners are optimal in doubling metrics
@@ Property / cites work: Greedy spanners are optimal in doubling metrics / rank @@
+Normal rank
@@ Property / cites work @@
+NEW SPARSENESS RESULTS ON GRAPH SPANNERS
@@ Property / cites work: NEW SPARSENESS RESULTS ON GRAPH SPANNERS / rank @@
+Normal rank
@@ Property / cites work @@
+Light Spanners
@@ Property / cites work: Light Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Constructions of Lightweight Spanners for General Graphs
+Normal rank
@@ Property / cites work @@
+Near-Optimal Light Spanners
@@ Property / cites work: Near-Optimal Light Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Additive spanners and (α, β)-spanners
@@ Property / cites work: Additive spanners and (α, β)-spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Low distortion spanners
@@ Property / cites work: Low distortion spanners / rank @@
+Normal rank
@@ Property / cites work @@
+On Pairwise Spanners
@@ Property / cites work: On Pairwise Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Small Stretch Pairwise Spanners
@@ Property / cites work: Small Stretch Pairwise Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+New pairwise spanners
@@ Property / cites work: New pairwise spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Spanners and emulators with sublinear distance errors
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Better Distance Preservers and Additive Spanners
@@ Property / cites work: Better Distance Preservers and Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
+Normal rank
@@ Property / cites work @@
+Q2921727
@@ Property / cites work: Q2921727 / rank @@
+Normal rank
@@ Property / cites work @@
+A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
+Normal rank
@@ Property / cites work @@
+New Additive Spanners
@@ Property / cites work: New Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
+Normal rank
@@ Property / cites work @@
+Sparse Distance Preservers and Additive Spanners
@@ Property / cites work: Sparse Distance Preservers and Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Sourcewise and Pairwise Distance Preservers
+Normal rank
@@ Property / cites work @@
+Error Amplification for Pairwise Spanner Lower Bounds
+Normal rank
@@ Property / cites work @@
+Linear Size Distance Preservers
@@ Property / cites work: Linear Size Distance Preservers / rank @@
+Normal rank
@@ Property / cites work @@
+Distance-Preserving Subgraphs of Interval Graphs
@@ Property / cites work: Distance-Preserving Subgraphs of Interval Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Unique Shortest Paths in Graphs
+Normal rank
@@ Property / cites work @@
+The 4/3 Additive Spanner Exponent Is Tight
@@ Property / cites work: The 4/3 Additive Spanner Exponent Is Tight / rank @@
+Normal rank
@@ Property / cites work @@
+Reachability Preservers: New Extremal Bounds and Approximation Algorithms
+Normal rank
@@ Property / cites work @@
+Terminal embeddings
@@ Property / cites work: Terminal embeddings / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
+Normal rank
@@ Property / cites work @@
+Q5116490
@@ Property / cites work: Q5116490 / rank @@
+Normal rank
@@ Property / cites work @@
+Additive Spanners in Nearly Quadratic Time
@@ Property / cites work: Additive Spanners in Nearly Quadratic Time / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111395
@@ Property / cites work: Q5111395 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
+Normal rank
@@ Property / cites work @@
+New (<i>α, β</i>) Spanners and Hopsets
@@ Property / cites work: New (<i>α, β</i>) Spanners and Hopsets / rank @@
+Normal rank
@@ Property / cites work @@
+Thorup-Zwick emulators are universally optimal hopsets
+Normal rank
@@ Property / cites work @@
+Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
+Normal rank
@@ Property / cites work @@
+Algorithms – ESA 2004
@@ Property / cites work: Algorithms – ESA 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Directed spanners via flow-based linear programs
@@ Property / cites work: Directed spanners via flow-based linear programs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for spanner problems and directed Steiner forest
+Normal rank
@@ Property / cites work @@
+Q2830866
@@ Property / cites work: Q2830866 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Low-Stretch Spanners
@@ Property / cites work: Approximating Low-Stretch Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Computing almost shortest paths
@@ Property / cites work: Computing almost shortest paths / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
+Normal rank
@@ Property / cites work @@
+Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
+Normal rank
@@ Property / cites work @@
+On the locality of distributed sparse spanner construction
+Normal rank
@@ Property / cites work @@
+Streaming algorithm for graph spanners-single pass and constant processing time per edge
+Normal rank
@@ Property / cites work @@
+Distributed algorithms for ultrasparse spanners and linear size skeletons
+Normal rank
@@ Property / cites work @@
+Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
+Normal rank
@@ Property / cites work @@
+Efficient distributed source detection with limited bandwidth
+Normal rank
@@ Property / cites work @@
+Spanners and sparsifiers in dynamic streams
@@ Property / cites work: Spanners and sparsifiers in dynamic streams / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed construction of purely additive spanners
+Normal rank
@@ Property / cites work @@
+The sparsest additive spanner via multiple weighted BFS trees
+Normal rank
@@ Property / cites work @@
+Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
+Normal rank
@@ Property / cites work @@
+On graph problems in a semi-streaming model
@@ Property / cites work: On graph problems in a semi-streaming model / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743413
@@ Property / cites work: Q5743413 / rank @@
+Normal rank
@@ Property / cites work @@
+All-Pairs Almost Shortest Paths
@@ Property / cites work: All-Pairs Almost Shortest Paths / rank @@
+Normal rank
@@ Property / cites work @@
+Q5009573
@@ Property / cites work: Q5009573 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles
@@ Property / cites work: Approximate distance oracles / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate distance oracles for unweighted graphs in expected             <i>O</i>             (             <i>n</i>             <sup>2</sup>             ) time
+Normal rank
@@ Property / cites work @@
+Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
+Normal rank
@@ Property / cites work @@
+Shortest-path queries in static networks
@@ Property / cites work: Shortest-path queries in static networks / rank @@
+Normal rank
@@ Property / cites work @@
+Towards tight approximation bounds for graph diameter and eccentricities
+Normal rank
@@ Property / cites work @@
+Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
+Normal rank
@@ Property / cites work @@
+Ramsey Spanning Trees and Their Applications
@@ Property / cites work: Ramsey Spanning Trees and Their Applications / rank @@
+Normal rank
@@ Property / cites work @@
+Spanners with Slack
@@ Property / cites work: Spanners with Slack / rank @@
+Normal rank
@@ Property / cites work @@
+Spanners in sparse graphs
@@ Property / cites work: Spanners in sparse graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q2766683
@@ Property / cites work: Q2766683 / rank @@
+Normal rank
@@ Property / cites work @@
+Tree Spanners
@@ Property / cites work: Tree Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
+Normal rank
@@ Property / cites work @@
+Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
+Normal rank
@@ Property / cites work @@
+Generating Low-Degree 2-Spanners
@@ Property / cites work: Generating Low-Degree 2-Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234097
@@ Property / cites work: Q4234097 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Euclidean Spanners
@@ Property / cites work: Optimal Euclidean Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+New Doubling Spanners: Better and Simpler
@@ Property / cites work: New Doubling Spanners: Better and Simpler / rank @@
+Normal rank
@@ Property / cites work @@
+Fault Tolerant Spanners for General Graphs
@@ Property / cites work: Fault Tolerant Spanners for General Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
+Normal rank
@@ Property / cites work @@
+Fault-tolerant spanners
@@ Property / cites work: Fault-tolerant spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Fault tolerant additive and \((\mu, \alpha)\)-spanners
+Normal rank
@@ Property / cites work @@
+Improved Purely Additive Fault-Tolerant Spanners
@@ Property / cites work: Improved Purely Additive Fault-Tolerant Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex fault tolerant additive spanners
@@ Property / cites work: Vertex fault tolerant additive spanners / rank @@
+Normal rank
@@ Property / cites work @@
+A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
+Normal rank
@@ Property / cites work @@
+Q4542536
@@ Property / cites work: Q4542536 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
+Normal rank
@@ Property / cites work @@
+Sparse Fault-Tolerant BFS Trees
@@ Property / cites work: Sparse Fault-Tolerant BFS Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Dual Failure Resilient BFS Structure
@@ Property / cites work: Dual Failure Resilient BFS Structure / rank @@
+Normal rank
@@ Property / cites work @@
+Multiple Source Dual Fault Tolerant BFS Trees
@@ Property / cites work: Multiple Source Dual Fault Tolerant BFS Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111404
@@ Property / cites work: Q5111404 / rank @@
+Normal rank
@@ Property / cites work @@
+On resilient graph spanners
@@ Property / cites work: On resilient graph spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Small Stretch Spanners on Dynamic Graphs
@@ Property / cites work: Small Stretch Spanners on Dynamic Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic Algorithms for Graph Spanners
@@ Property / cites work: Dynamic Algorithms for Graph Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Fully dynamic randomized algorithms for graph spanners
+Normal rank
@@ Property / cites work @@
+Q4606286
@@ Property / cites work: Q4606286 / rank @@
+Normal rank
@@ Property / cites work @@
+A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
+Normal rank
@@ Property / cites work @@
+Q4829021
@@ Property / cites work: Q4829021 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation for the Directed Spanner Problem
+Normal rank
@@ Property / cites work @@
+Source-wise round-trip spanners
@@ Property / cites work: Source-wise round-trip spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic improved round-trip spanners
@@ Property / cites work: Deterministic improved round-trip spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Polylog-time and near-linear work approximation scheme for undirected shortest paths
+Normal rank
@@ Property / cites work @@
+Concurrent counting is harder than queuing
@@ Property / cites work: Concurrent counting is harder than queuing / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Visibility Information in an Inaccurate Simple Polygon
+Normal rank
@@ Property / cites work @@
+Reconstructing the shape of a tree from observed dissimilarity data
+Normal rank
@@ Property / DOI @@
+.1016/J.COSREV.2020.100253
@@ Property / DOI: 10.1016/J.COSREV.2020.100253 / rank @@
+Normal rank