Computing geometric minimum-dilation graphs is NP-hard
DOI10.1142/S0218195910003244zbMATH Open1203.05154OpenAlexW2137045378MaRDI QIDQ3562852FDOQ3562852
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
Recommendations
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)
Cites Work
- Geometric Spanner Networks
- Minimum-weight triangulation is NP-hard
- Hamilton Paths in Grid Graphs
- Tree Spanners
- Tree spanners in planar graphs
- The geometric dilation of finite point sets
- ON SPANNERS OF GEOMETRIC GRAPHS
- Computing a minimum-dilation spanning tree is NP-hard
- Improving the Stretch Factor of a Geometric Network by Edge Augmentation
- Minimum dilation stars
- NP-completeness of minimum spanner problems
- Sparse geometric graphs with small dilation
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)
