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