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.68066MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
The binary locating-dominating number of some convex polytopes, Unnamed Item, On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs, Identifying Codes in Line Graphs, Complexity and approximation for discriminating and identifying code problems in geometric setups, On three domination-based identification problems in block graphs, More results on the complexity of identifying problems in graphs, On the ensemble of optimal identifying codes in a twin-free graph, A comparison of approaches for finding minimum identifying codes on graphs, A polyhedral approach to locating-dominating sets in graphs, The minimum identifying code graphs, On the number of optimal identifying codes in a twin-free graph, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., Identifying codes in some subgraphs of the square lattice, Identifying codes and locating-dominating sets on paths and cycles, Combinatorial identification problems and graph powers, On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs, On locating--dominating sets in infinite grids, Extremal cardinalities for identifying and locating-dominating codes in graphs, Identifying codes in vertex-transitive graphs and strongly regular graphs, Identifying codes of cycles with odd orders, Minimal identifying codes in trees and planar graphs with large girth, Localization game on geometric and planar graphs, Locating-dominating sets in hypergraphs, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, Separating codes and traffic monitoring, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, 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, On identification in the triangular grid, Identifying and locating-dominating codes on chains and cycles, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, On locating-dominating set of regular graphs, Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs, 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, On the watching number of graphs using discharging procedure, The watching system as a generalization of identifying code, Domination parameters in hypertrees and sibling trees, Linear-time algorithms for three domination-based separation problems in block graphs, Covering codes of a graph associated with a finite vector space, New results of identifying codes in product graphs, Set graphs. II. Complexity of set graph recognition and similar problems, Locating-dominating codes in paths, On two variations of identifying codes, Alternative parameterizations of \textsc{Metric Dimension}, 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, A note on the locating-total domination in graphs, Approximability of identifying codes and locating-dominating codes, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, A linear-time algorithm for the identifying code problem on block graphs, Identifying codes on directed de Bruijn graphs, Extremal graphs for the identifying code problem, An optimal locating-dominating set in the infinite triangular grid, Identifying codes of corona product graphs, Locating sensors in paths and cycles: the case of 2-identifying codes, Identifying codes of cycles, A linear algorithm for minimum 1-identifying codes in oriented trees, On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\), On redundant locating-dominating sets, Unnamed Item, Domination Parameters in Hypertrees, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Separating Codes and Traffic Monitoring, Identifying Codes in Trees and Planar Graphs, Identifying codes and watching systems in Kneser graphs, Complexity results for identifying codes in planar graphs, Locating-Domination and Identification, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, Identifying and Locating–Dominating Codes in (Random) Geometric Networks
Cites Work
