Efficient construction of a bounded-degree spanner with low weight

DOI10.1007/BF02523237zbMath0864.68108MaRDI QIDQ2365175

Sunil Arya, Michiel H. M. Smid

Publication date: 9 June 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

greedy algorithmdistance enumeration

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (11)

Euclidean Steiner Spanners: Light and Sparse ⋮ EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER ⋮ Truly Optimal Euclidean Spanners ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Sparse communication networks and efficient routing in the plane ⋮ Light Euclidean Spanners with Steiner Points ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Deformable spanners and applications ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic fractional cascading
• Maintaining the minimal distance of a point set in polylogarithmic time
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• ENUMERATING INTERDISTANCES IN SPACE
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS

This page was built for publication: Efficient construction of a bounded-degree spanner with low weight