Back to Search
Start Over
The Inverse Voronoi Problem in Graphs I: Hardness.
- Source :
-
Algorithmica . Oct2020, Vol. 82 Issue 10, p3018-3040. 23p. - Publication Year :
- 2020
-
Abstract
- We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection U of subsets of vertices of V(G), decide whether U is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 82
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 146034561
- Full Text :
- https://doi.org/10.1007/s00453-020-00716-4