ON SPANNERS OF GEOMETRIC GRAPHS

DOI10.1142/S0129054109006486zbMath1170.68546OpenAlexW2167511304MaRDI QIDQ3620618

Joachim Gudmundsson, Michiel H. M. Smid

Publication date: 14 April 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

optimizationNP-hardgeometric spanners

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD

Cites Work

• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• Restrictions of minimum spanner problems
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Geometric Spanner Networks
• Graph spanners
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• A High Girth Graph Construction
• Tree Spanners

This page was built for publication: ON SPANNERS OF GEOMETRIC GRAPHS