Computing Geometric Minimum-Dilation Graphs is NP-Hard

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

doi:10.1142/S0218195910003244

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

Reference:

Computing Geometric Minimum-Dilation Graphs is NP-Hard (Panos Giannopoulos, Rolf Klein, Christian Knauer, Martin Kutz, Dániel Marx), In Int. J. Comput. Geometry Appl., volume 20, 2010.

Bibtex Entry:

@article{journals/ijcga/Computing_Geometric_Minimum-Dilation_Graphs_is_NP-Hard,
  author    = {Panos Giannopoulos and
               Rolf Klein and
               Christian Knauer and
               Martin Kutz and
               D{\'a}niel Marx},
  title     = {Computing Geometric Minimum-Dilation Graphs is NP-Hard},
  journal   = {Int. J. Comput. Geometry Appl.},
  volume    = {20},
  number    = {2},
  year      = {2010},
  pages     = {147-173},
  doi       = {10.1142/S0218195910003244},
  urlx      = {http://www.ai6.uni-bayreuth.de/uploads/pdf/.pdf}
}