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

DOI10.1109/TIT.2002.800490zbMath1062.94056OpenAlexW2140429404MaRDI 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

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial codes (94B25)

Related Items

On locating--dominating sets in infinite grids ⋮ Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets ⋮ Approximability of identifying codes and locating-dominating codes ⋮ Locating-dominating sets in hypergraphs ⋮ Identifying path covers in graphs ⋮ Set graphs. IV. Further connections with claw-freeness ⋮ Identifying codes in line digraphs ⋮ 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 ⋮ The binary locating-dominating number of some convex polytopes ⋮ An optimal locating-dominating set in the infinite triangular grid ⋮ Identifying codes and locating-dominating sets on paths and cycles ⋮ Covering codes of a graph associated with a finite vector space ⋮ Locating sensors in paths and cycles: the case of 2-identifying codes ⋮ 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 ⋮ A linear algorithm for minimum 1-identifying codes in oriented trees ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ Locating-Domination and Identification ⋮ On identification in the triangular grid ⋮ Domination and location in twin-free digraphs ⋮ Locating-dominating sets of functigraphs ⋮ Locating-dominating sets: from graphs to oriented graphs ⋮ Binary locating-dominating sets in rotationally-symmetric convex polytopes