Computing a minimum-dilation spanning tree is NP-hard

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

Mi Ra Lee, Herman J. Haverkort, Otfried Schwarzkopf

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

optimizationshortest pathdilationspanning treeNP-hardnessgeometric networkspanner

Mathematics Subject Classification ID

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

Related Items (16)

On the dilation spectrum of paths, cycles, and trees ⋮ SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES ⋮ Optimal Embedding into Star Metrics ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Computing Minimum Dilation Spanning Trees in Geometric Graphs ⋮ On plane geometric spanners: a survey and open problems ⋮ An exact algorithm for the minimum dilation triangulation problem ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ General variable neighborhood search for the minimum stretch spanning tree problem ⋮ Sparse geometric graphs with small dilation ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Unnamed Item ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lattice spanners of low degree ⋮ On the Stretch Factor of Polygonal Chains

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

This page was built for publication: Computing a minimum-dilation spanning tree is NP-hard