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