NEW SPARSENESS RESULTS ON GRAPH SPANNERS
From MaRDI portal
Publication:4698355
DOI10.1142/S0218195995000088zbMath0818.68078OpenAlexW2114585066MaRDI QIDQ4698355
No author found.
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
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (41)
\( \delta \)-greedy \(t\)-spanner ⋮ Efficient construction of a bounded-degree spanner with low weight ⋮ Constructing sparse spanners for most graphs in higher dimensions ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Balancing minimum spanning trees and shortest-path trees ⋮ EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER ⋮ Truly Optimal Euclidean Spanners ⋮ Restrictions of minimum spanner problems ⋮ Covering metric spaces by few trees ⋮ Near isometric terminal embeddings for doubling metrics ⋮ On additive spanners in weighted graphs with local error ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ Unnamed Item ⋮ The MST of symmetric disk graphs is light ⋮ Unnamed Item ⋮ On dynamic shortest paths problems ⋮ Computing the greedy spanner in near-quadratic time ⋮ Sparse geometric graphs with small dilation ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ Edge-disjoint spanners in Cartesian products of graphs ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ The Minimal Manhattan Network Problem in Three Dimensions ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Light orthogonal networks with constant geometric dilation ⋮ Lattice spanners of low degree ⋮ Covering Metric Spaces by Few Trees ⋮ Edge-disjoint spanners in tori ⋮ 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 ⋮ Light Spanners ⋮ Constructing light spanners deterministically in near-linear time ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Edge-disjoint spanners of complete graphs and complete digraphs
This page was built for publication: NEW SPARSENESS RESULTS ON GRAPH SPANNERS
