Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
From MaRDI portal
Publication:1401220
DOI10.1016/S0304-3975(02)00536-4zbMath1044.68066OpenAlexW1967536892MaRDI QIDQ1401220
Olivier Hudry, Irène Charon, Antoine C. Lobstein
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00536-4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (77)
More results on the complexity of identifying problems in graphs ⋮ On locating--dominating sets in infinite grids ⋮ On the ensemble of optimal identifying codes in a twin-free graph ⋮ A note on the locating-total domination in graphs ⋮ Identifying and locating-dominating codes on chains and cycles ⋮ The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Identifying codes in the complementary prism of cycles ⋮ Localization game on geometric and planar graphs ⋮ A comparison of approaches for finding minimum identifying codes on graphs ⋮ Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ On the watching number of graphs using discharging procedure ⋮ Approximability of identifying codes and locating-dominating codes ⋮ A polyhedral approach to locating-dominating sets in graphs ⋮ Extremal cardinalities for identifying and locating-dominating codes in graphs ⋮ Identifying codes in some subgraphs of the square lattice ⋮ Identifying Codes in Line Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Locating-dominating sets in hypergraphs ⋮ The watching system as a generalization of identifying code ⋮ Domination parameters in hypertrees and sibling trees ⋮ A linear-time algorithm for the identifying code problem on block graphs ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Identifying codes on directed de Bruijn graphs ⋮ Identifying codes in vertex-transitive graphs and strongly regular graphs ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results ⋮ On three domination-based identification problems in block graphs ⋮ On redundant locating-dominating sets ⋮ The minimum identifying code graphs ⋮ On the binary locating-domination number of regular and strongly-regular graphs ⋮ Extremal graphs for the identifying code problem ⋮ Identifying codes and watching systems in Kneser graphs ⋮ The binary locating-dominating number of some convex polytopes ⋮ An optimal locating-dominating set in the infinite triangular grid ⋮ Separating codes and traffic monitoring ⋮ Identifying codes and locating-dominating sets on paths and cycles ⋮ Covering codes of a graph associated with a finite vector space ⋮ Identifying codes of corona product graphs ⋮ On the number of optimal identifying codes in a twin-free graph ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Complexity results for identifying codes in planar graphs ⋮ Locating sensors in paths and cycles: the case of 2-identifying codes ⋮ Identifying codes of cycles with odd orders ⋮ Identifying and Locating–Dominating Codes in (Random) Geometric Networks ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ New results of identifying codes in product graphs ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ Operads of finite posets ⋮ On the minimum size of an identifying code over all orientations of a graph ⋮ Set graphs. II. Complexity of set graph recognition and similar problems ⋮ Identifying codes of cycles ⋮ Unnamed Item ⋮ Minimal identifying codes in trees and planar graphs with large girth ⋮ A linear algorithm for minimum 1-identifying codes in oriented trees ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-dominating codes in paths ⋮ On two variations of identifying codes ⋮ On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\) ⋮ Domination Parameters in Hypertrees ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ On locating-dominating set of regular graphs ⋮ Locating-Domination and Identification ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Separating Codes and Traffic Monitoring ⋮ Unnamed Item ⋮ Combinatorial identification problems and graph powers ⋮ On identification in the triangular grid ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Identifying Codes in Trees and Planar Graphs ⋮ Locating-dominating sets of functigraphs ⋮ Binary locating-dominating sets in rotationally-symmetric convex polytopes ⋮ Locating-paired-dominating sets in square grids ⋮ Computing the metric dimension for chain graphs
Cites Work
This page was built for publication: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
