Computing geometric minimum-dilation graphs is NP-hard

DOI10.1142/S0218195910003244MaRDI QIDQ3562852zbMATH OpenOpenAlexFDO

Authors Panos Giannopoulos, Rolf Klein, Christian Knauer, Dániel Marx, 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

dilationgeometric networkNP-hardnessplane graphpathstretch factorspanning ratiotour

Mathematics Subject Classification ID

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

Recommendations

• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Computing a minimum-dilation spanning tree is NP-hard
• Computing minimum dilation spanning trees in geometric graphs
• SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES
• Fixed edge-length graph drawing is NP-hard

Cites work

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

Cited in

(8)

• Hardness results for computing optimal locally Gabriel graphs
• SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES
• Optimal spanners for axis-aligned rectangles
• Planar subgraphs without low-degree nodes
• Hardness of minimum barrier shrinkage and minimum installation path
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• An exact algorithm for the minimum dilation triangulation problem
• Computing a minimum-dilation spanning tree is NP-hard

This page was built for publication: Computing geometric minimum-dilation graphs is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3562852)