Minimum weight Euclidean \(t\)-spanner is NP-hard

DOI10.1016/j.jda.2013.06.010zbMath1334.68238arXiv1209.0679OpenAlexW2026144971MaRDI QIDQ396666

Lilach Chaitman-Yerushalmi, Paz Carmi

Publication date: 13 August 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.0679

zbMATH Keywords

computational geometryNP-hardnessgeometry spanner

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Geometric spanning trees minimizing the Wiener index ⋮ Unnamed Item ⋮ Minimizing the sum of distances to a server in a constraint network

Cites Work

• Unnamed Item
• Unnamed Item
• Computing a minimum-dilation spanning tree is NP-hard
• Geometric Spanner Networks
• Computing the Greedy Spanner in Near-Quadratic Time
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• ON SPANNERS OF GEOMETRIC GRAPHS
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Tree Spanners
• Reducibility among Combinatorial Problems

This page was built for publication: Minimum weight Euclidean \(t\)-spanner is NP-hard