The inverse Voronoi problem in graphs. I: Hardness

DOI10.1007/S00453-020-00716-4MaRDI QIDQ2006948zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, S. Cabello, Bojan Mohar, Hebert Pérez-Rosés

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

zbMATH Keywords

distances in graphsinverse Voronoi problemNP-completenessparameterized complexityVoronoi diagram

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The inverse Voronoi problem in graphs. II: Trees
• Inverse problems in the theory of distance-regular graphs
• On an extremal inverse problem in graph theory
• Inverse eccentric vertex problem on networks
• Inverse problems of graph theory: generalized quadrangles
• Inverse problems in graph theory: nets
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• Inverse Problems and Zero Forcing for Graphs
• scientific article; zbMATH DE number 1341907
• scientific article; zbMATH DE number 3908459

Cites work

• Advantage in the discrete Voronoi game
• An algorithm for a selective nearest neighbor decision rule (Corresp.)
• Better tradeoffs for exact distance oracles in planar graphs
• Can you beat treewidth?
• Fitting Voronoi diagrams to planar tesselations
• Graph reconstruction and verification
• scientific article; zbMATH DE number 1542607 (Why is no real title available?)
• Interval graphs and searching
• Minimum-weight triangulation is NP-hard
• Near-Optimal Sample Compression for Nearest Neighbors
• On the complexity of k-SAT
• On the Construction of Generalized Voronoi Inverse of a Rectangular Tessellation
• On the minimum consistent subset problem
• Parameterized algorithms
• Planar Formulae and Their Uses
• Recognizing Dirichlet tesselations
• Shortest cut graph of a surface with prescribed vertex set
• Spatial Analysis along Networks
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Voronoi game on graphs
• Which problems have strongly exponential complexity?

Cited in

(8)

• Minimum consistent subset problem for trees
• The inverse Voronoi problem in graphs. II: Trees
• Fitting Voronoi diagrams to planar tesselations
• Minimum consistent subset of simple graph classes
• Balancing graph Voronoi diagrams with one more vertex
• Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
• Can you link up with treewidth?
• Can you link up with treewidth?

Describes a project that uses

Uses Software

• SANET

This page was built for publication: The inverse Voronoi problem in graphs. I: Hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006948)