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
Irène Charon, Olivier Hudry, Antoine C. Lobstein
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Identifying Codes in Line 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 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, Locating-dominating sets in hypergraphs, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, 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, Set graphs. II. Complexity of set graph recognition and similar problems, Locating-dominating codes in paths, On two variations of identifying codes, 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, 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\), 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, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, Identifying and Locating–Dominating Codes in (Random) Geometric Networks
Cites Work
