scientific article; zbMATH DE number 910877

MaRDI QIDQ4886051zbMATH OpenFDO

Authors Giri Narasimhan, Jeffrey S. Salowe, Gautam K. Das

Publication date 4 November 1996

zbMATH Keywords

Euclidean graphSteiner minimal trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Optimal Euclidean Spanners
• Euclidean Steiner spanners: light and sparse
• Approximating Euclidean distances by small degree graphs
• On sparse spanners of weighted graphs

Cited in

(18)

• Local routing in sparse and lightweight geometric graphs
• Efficient construction of a bounded-degree spanner with low weight
• On certain geometric properties of the Yao-Yao graphs
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
• Minimum weight Euclidean t-spanner is NP-hard
• Euclidean Steiner spanners: light and sparse
• Truly Optimal Euclidean Spanners
• Light Euclidean Spanners with Steiner Points
• Minimum weight Euclidean (1+)-spanners
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• A unified framework for light spanners
• An improved upper bound for the universal TSP on the grid
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• Truly optimal Euclidean spanners
• Online Euclidean spanners
• On euclidean Steiner (1+)-spanners
• Light Euclidean Steiner spanners in the plane
• Light spanners with small hop-diameter

This page was built for publication:

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