A Fast Algorithm for Constructing Sparse Euclidean Spanners

DOI10.1142/S0218195997000193zbMath0883.68117OpenAlexW2148073303MaRDI QIDQ4354006

Giri Narasimhan, Gautam K. Das

Publication date: 10 September 1997

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195997000193

zbMATH Keywords

\(t\)-spannersgraph clustering techniques

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (18)

\( \delta \)-greedy \(t\)-spanner ⋮ Distributed construction of low-interference spanners ⋮ EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ Computing the greedy spanner in near-quadratic time ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Constructing minimum-interference networks ⋮ Shortest-Path Queries in Geometric Networks ⋮ Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies ⋮ The Minimal Manhattan Network Problem in Three Dimensions ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Region-fault tolerant geometric spanners ⋮ Constructing light spanners deterministically in near-linear time

This page was built for publication: A Fast Algorithm for Constructing Sparse Euclidean Spanners