Minimum weight Euclidean \((1+\varepsilon)\)-spanners

Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Theta-3 is connected
\( \delta \)-greedy \(t\)-spanner
Improved bounds on the spanning ratio of the theta-5-graph
Towards tight bounds on theta-graphs: more is not always better
An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
Low-light trees, and tight lower bounds for Euclidean spanners
Classes of graphs which approximate the complete Euclidean graph
On sparse spanners of weighted graphs
Approximation of real numbers by rationals: some metric theorems
The discrepancy of Farey series
Discrepancy of Farey sequences
On the spanning and routing ratios of the directed \(\Theta_6\)-graph
A spanner for the day after
Efficient construction of a bounded-degree spanner with low weight
Deformable spanners and applications
Lattice spanners of low degree
Balancing Degree, Diameter, and Weight in Euclidean Spanners
New and improved spanning ratios for Yao graphs
Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
Optimal Euclidean Spanners
The shortest path and the shortest road through n points
On Locality-Sensitive Orderings and Their Applications
Geometric Spanner Networks
Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
The Travelling Salesman Problem and Minimum Matching in the Unit Square
A Fast Algorithm for Constructing Sparse Euclidean Spanners
The Greedy Spanner Is Existentially Optimal
Euclidean Steiner Spanners: Light and Sparse
Truly Optimal Euclidean Spanners
Greedy spanners are optimal in doubling metrics
A note on optimal degree-three spanners of the square lattice
Light Euclidean Spanners with Steiner Points
Fully dynamic geometric spanners
Improved algorithms for constructing fault-tolerant spanners