Identifying and locating-dominating codes: NP-completeness results for directed graphs

DOI10.1109/TIT.2002.800490zbMath1062.94056MaRDI QIDQ4677540

Irène Charon, Olivier Hudry, Antoine C. Lobstein

Publication date: 11 May 2005

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2002.800490

Mathematics Subject Classification ID

05C90: Applications of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

94B25: Combinatorial codes

Related Items

The binary locating-dominating number of some convex polytopes, Locating-dominating sets in local tournaments, On the binary locating-domination number of regular and strongly-regular graphs, Extremal Digraphs for open neighbourhood location-domination and identifying codes, Identifying path covers in graphs, Set graphs. IV. Further connections with claw-freeness, Identifying codes and locating-dominating sets on paths and cycles, Domination and location in twin-free digraphs, On locating--dominating sets in infinite grids, Locating-dominating sets in hypergraphs, Operads of finite posets, On the minimum size of an identifying code over all orientations of a graph, On identification in the triangular grid, Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code, Locating-dominating sets: from graphs to oriented graphs, Identifying codes in line digraphs, Covering codes of a graph associated with a finite vector space, Set graphs. II. Complexity of set graph recognition and similar problems, Locating-dominating sets of functigraphs, Binary locating-dominating sets in rotationally-symmetric convex polytopes, Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets, Approximability of identifying codes and locating-dominating codes, An optimal locating-dominating set in the infinite triangular grid, Locating sensors in paths and cycles: the case of 2-identifying codes, A linear algorithm for minimum 1-identifying codes in oriented trees, Locating-Domination and Identification