Recommendations
- Spanners in Sparse Graphs
- Spanners in sparse graphs
- A New Combinatorial Approach for Sparse Graph Problems
- On sparse spanners of weighted graphs
- Sparse hypergraphs: new bounds and constructions
- scientific article; zbMATH DE number 434498
- Sparsification lower bound for linear spanners in directed graphs
- The emergence of sparse spanners and greedy well-separated pair decomposition
- Sparsity. Graphs, structures, and algorithms
Cited in
(70)- \( \delta \)-greedy \(t\)-spanner
- scientific article; zbMATH DE number 7238981 (Why is no real title available?)
- Lower bounds on the dilation of plane spanners
- New (α, β) Spanners and Hopsets
- scientific article; zbMATH DE number 910877 (Why is no real title available?)
- Graph spanners: a tutorial review
- Sparse geometric graphs with small dilation
- Minimum weight Euclidean t-spanner is NP-hard
- Constructing Light Spanners Deterministically in Near-Linear Time
- Efficient construction of a bounded-degree spanner with low weight
- Edge-disjoint spanners in tori
- Diameter-preserving spanning trees in sparse weighted graphs
- Constructing sparse spanners for most graphs in higher dimensions
- An alternate proof of near-optimal light spanners
- Generating sparse spanners for weighted graphs
- Lasserre integrality gaps for graph spanners and related problems
- Covering Metric Spaces by Few Trees
- Small hop-diameter sparse spanners for doubling metrics
- Geometric spanners for weighted point sets
- The emergence of sparse spanners and well-separated pair decomposition under anarchy
- The MST of symmetric disk graphs is light
- Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
- Light orthogonal networks with constant geometric dilation
- Computing the greedy spanner in near-quadratic time
- Light spanners
- Light spanners
- Routing on heavy path WSPD spanners
- Lattice spanners of low degree
- Spanners in randomly weighted graphs: Euclidean case
- On sparse spanners of weighted graphs
- Lattice spanners of low degree
- Truly Optimal Euclidean Spanners
- scientific article; zbMATH DE number 7378699 (Why is no real title available?)
- Vertex Sparsifiers: New Results from Old Techniques
- Lower bounds on the dilation of plane spanners
- scientific article; zbMATH DE number 7561533 (Why is no real title available?)
- Approximating \(k\)-spanner problems for \(k>2\)
- Lower bound for sparse Euclidean spanners
- scientific article; zbMATH DE number 1617269 (Why is no real title available?)
- Fine-grained complexity for sparse graphs
- Restrictions of minimum spanner problems
- Near isometric terminal embeddings for doubling metrics
- Edge-disjoint spanners of complete graphs and complete digraphs
- Covering metric spaces by few trees
- Near isometric terminal embeddings for doubling metrics
- Sparsification lower bound for linear spanners in directed graphs
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Algorithms – ESA 2004
- Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
- On dynamic shortest paths problems
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- On additive spanners in weighted graphs with local error
- Constructing sparse t-spanners with small separators.
- Geometric Spanners for Weighted Point Sets
- Spanners in randomly weighted graphs: independent edge lengths
- scientific article; zbMATH DE number 7650078 (Why is no real title available?)
- A unified framework for light spanners
- Spanners in Sparse Graphs
- The Minimal Manhattan Network Problem in Three Dimensions
- Algorithms and Computation
- The greedy spanner is existentially optimal
- Constructing light spanners deterministically in near-linear time
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Balancing minimum spanning trees and shortest-path trees
- Edge-disjoint spanners in Cartesian products of graphs
- Light spanners for high dimensional norms via stochastic decompositions
- Improving the crossing lemma by finding more crossings in sparse graphs
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
This page was built for publication: NEW SPARSENESS RESULTS ON GRAPH SPANNERS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4698355)
