Volume: 20, Issue: 2(2010)
pp. 147-173 DOI: 10.1142/S0218195910003244
|
|
Abstract |
Full Text (PDF, 488KB)
|
References
|
 |
| Title: |
COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD |
| Author(s): |
PANOS GIANNOPOULOS
Partially supported by the DFG project no. GR 1492/7-2.
Humboldt- Universität zu Berlin, Institut für Informatik, Unter den Linden 6, D-10099 Berlin, GermanyROLF KLEIN
Partially supported by the German Research Foundation DFG, grant no. Kl 655/ 14-1/2/3.
Institute of Computer Science I, 53117 Bonn, GermanyCHRISTIAN KNAUER
Institut für Informatik, Freie Universität Berlin, Takustraße 9, D-14195 Berlin, GermanyMARTIN KUTZ
Max-Planck-Institut für Informatik, 66123 Saarbrücken, GermanyDÁNIEL MARX
Humboldt-Universität zu Berlin, Institut für Informatik, Unter den Linden 6, D-10099 Berlin, Germany
|
| History: |
Received 16 August 2007
Revised 18 September 2009
|
| Abstract: |
We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case. |
| Keywords: |
Dilation; geometric network; plane graph; tour; path; spanning ratio; stretch factor; NP-hardness
|
|
|
