Computing a minimum-dilation spanning tree is NP-hard

DOI10.1016/j.comgeo.2007.12.001zbMath1188.65018MaRDI QIDQ945943

Otfried Schwarzkopf, Herman J. Haverkort, Mi Ra Lee

Publication date: 19 September 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.12.001

zbMATH Keywords

optimization; shortest path; dilation; spanning tree; NP-hardness; geometric network; spanner

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES, On plane geometric spanners: a survey and open problems, On the dilation spectrum of paths, cycles, and trees, Sparse geometric graphs with small dilation, Optimal Embedding into Star Metrics, COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD

Cites Work

• Unnamed Item
• Unnamed Item
• Sparse geometric graphs with small dilation
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Algorithms – ESA 2005
• Tree spanners in planar graphs