The inverse Voronoi problem in graphs. I: Hardness
Publication:2006948
DOI10.1007/S00453-020-00716-4zbMath1455.68135OpenAlexW3027090837MaRDI QIDQ2006948
Édouard Bonnet, Hebert Pérez-Rosés, Bojan Mohar, Sergio Cabello
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
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Voronoi game on graphs
- Interval graphs and searching
- Recognizing Dirichlet tesselations
- Which problems have strongly exponential complexity?
- Graph induced complex on point data
- On the Construction of Generalized Voronoi Inverse of a Rectangular Tessellation
- Fitting Voronoi Diagrams to Planar Tesselations
- Advantage in the discrete Voronoi game
- Spatial Analysis along Networks
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Minimum-weight triangulation is NP-hard
- Shortest Cut Graph of a Surface with Prescribed Vertex Set
- Planar Formulae and Their Uses
- An algorithm for a selective nearest neighbor decision rule (Corresp.)
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Graph Reconstruction and Verification
- Near-Optimal Sample Compression for Nearest Neighbors
- Parameterized Algorithms
- On the minimum consistent subset problem
- On the complexity of \(k\)-SAT
This page was built for publication: The inverse Voronoi problem in graphs. I: Hardness
