NEW SPARSENESS RESULTS ON GRAPH SPANNERS
From MaRDI portal
Publication:4698355
DOI10.1142/S0218195995000088zbMATH Open0818.68078OpenAlexW2114585066MaRDI QIDQ4698355FDOQ4698355
Author name not available (Why is that?)
Publication date: 17 May 1995
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195995000088
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
- 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
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Cited In (61)
- Routing on heavy path WSPD spanners
- A unified framework for light spanners
- Light Spanners
- \( \delta \)-greedy \(t\)-spanner
- Near Isometric Terminal Embeddings for Doubling Metrics
- Graph spanners: a tutorial review
- Sparse geometric graphs with small dilation
- Constructing Light Spanners Deterministically in Near-Linear Time
- Minimum weight Euclidean \(t\)-spanner is NP-hard
- Efficient construction of a bounded-degree spanner with low weight
- Edge-disjoint spanners in tori
- Constructing sparse spanners for most graphs in higher dimensions
- Generating sparse spanners for weighted graphs
- Covering Metric Spaces by Few Trees
- Lasserre integrality gaps for graph spanners and related problems
- Small hop-diameter sparse spanners for doubling metrics
- Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
- The MST of symmetric disk graphs is light
- Light orthogonal networks with constant geometric dilation
- Computing the greedy spanner in near-quadratic time
- Spanners in randomly weighted graphs: Euclidean case
- The Greedy Spanner Is Existentially Optimal
- Lattice Spanners of Low Degree
- Lattice spanners of low degree
- On sparse spanners of weighted graphs
- Truly Optimal Euclidean Spanners
- Title not available (Why is that?)
- Vertex Sparsifiers: New Results from Old Techniques
- Lower Bounds on the Dilation of Plane Spanners
- Title not available (Why is that?)
- Fine-grained complexity for sparse graphs
- Title not available (Why is that?)
- Approximating \(k\)-spanner problems for \(k>2\)
- Restrictions of minimum spanner problems
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Covering metric spaces by few trees
- Near isometric terminal embeddings for doubling metrics
- Edge-disjoint spanners of complete graphs and complete digraphs
- Sparsification lower bound for linear spanners in directed graphs
- Algorithms – ESA 2004
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- On additive spanners in weighted graphs with local error
- On dynamic shortest paths problems
- Geometric Spanners for Weighted Point Sets
- Title not available (Why is that?)
- Spanners in Sparse Graphs
- The Minimal Manhattan Network Problem in Three Dimensions
- Algorithms and Computation
- 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
- Improving the crossing lemma by finding more crossings in sparse graphs
- Edge-disjoint spanners in Cartesian products of graphs
- Light spanners for high dimensional norms via stochastic decompositions
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Lower bounds on the dilation of plane spanners
- Title not available (Why is that?)
- New (α, β) Spanners and Hopsets
- Title not available (Why is that?)
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)
