COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD

DOI10.1142/S0218195910003244zbMath1203.05154OpenAlexW2137045378MaRDI QIDQ3562852

Panos Giannopoulos, Dániel Marx, Christian Knauer, Rolf Klein, Martin Kuetz

Publication date: 28 May 2010

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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

zbMATH Keywords

dilationpathplane graphNP-hardnessgeometric networkstretch factorspanning ratiotour

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES, HARDNESS RESULTS FOR COMPUTING OPTIMAL LOCALLY GABRIEL GRAPHS, An exact algorithm for the minimum dilation triangulation problem

Cites Work

• Minimum dilation stars
• Sparse geometric graphs with small dilation
• Computing a minimum-dilation spanning tree is NP-hard
• NP-completeness of minimum spanner problems
• The geometric dilation of finite point sets
• Geometric Spanner Networks
• Minimum-weight triangulation is NP-hard
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• ON SPANNERS OF GEOMETRIC GRAPHS
• Hamilton Paths in Grid Graphs
• Tree Spanners
• Tree spanners in planar graphs