The inverse Voronoi problem in graphs. I: Hardness
DOI10.1007/s00453-020-00716-4zbMath1455.68135MaRDI QIDQ2006948
Bojan Mohar, Sergio Cabello, Hebert Pérez-Rosés, Édouard Bonnet
Publication date: 12 October 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00716-4
NP-completeness; Voronoi diagram; parameterized complexity; distances in graphs; inverse Voronoi problem
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27: Parameterized complexity, tractability and kernelization
Uses Software
