A Fast Algorithm for Constructing Sparse Euclidean Spanners

DOI10.1142/S0218195997000193MaRDI QIDQ4354006zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• An optimal-time construction of sparse Euclidean spanners with tiny diameter
• Sparse Euclidean Spanners with Tiny Diameter
• Lower bound for sparse Euclidean spanners
• Efficient algorithms for constructing very sparse spanners and emulators
• Efficient algorithms for constructing very sparse spanners and emulators
• Euclidean spanners in high dimensions
• scientific article; zbMATH DE number 1617269
• Euclidean Steiner spanners: light and sparse

Cited in

(30)

• Region-fault tolerant geometric spanners
• Computing the greedy spanner in near-quadratic time
• Constructing light spanners deterministically in near-linear time
• Distributed construction of low-interference spanners
• scientific article; zbMATH DE number 1617269 (Why is no real title available?)
• Sparse Euclidean Spanners with Tiny Diameter
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Computing the Greedy Spanner in Near-Quadratic Time
• Testing Euclidean Spanners
• The Minimal Manhattan Network Problem in Three Dimensions
• Minimum weight Euclidean t-spanner is NP-hard
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• The greedy spanner is existentially optimal
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Constructing Light Spanners Deterministically in Near-Linear Time
• STACS 2005
• Shortest-Path Queries in Geometric Networks
• Online Euclidean Spanners
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• A unified framework for light spanners
• A simple and efficient method for accelerating construction of the gap-greedy spanner
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
• A divide-and-conquer based preprocessing for routing in a simple polygon
• On the edge crossings of the greedy spanner
• \( \delta \)-greedy \(t\)-spanner
• Constructing minimum-interference networks
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354006)