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, Lower Bounds on the Dilation of Plane Spanners, On plane geometric spanners: a survey and open problems, Minimum weight Euclidean \(t\)-spanner is NP-hard, On the dilation spectrum of paths, cycles, and trees, Sparse geometric graphs with small dilation, An exact algorithm for the minimum dilation triangulation problem, Lattice Spanners of Low Degree, Lattice spanners of low degree, Optimal Embedding into Star Metrics, Computing Minimum Dilation Spanning Trees in Geometric Graphs, SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES, 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