Identifying and locating-dominating codes: NP-completeness results for directed graphs
DOI10.1109/TIT.2002.800490zbMATH Open1062.94056OpenAlexW2140429404MaRDI QIDQ4677540FDOQ4677540
Authors: Irène Charon, Olivier Hudry, Antoine 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
Recommendations
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Complexity results for identifying codes in planar graphs
- On the minimum size of an identifying code over all orientations of a graph
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial codes (94B25)
Cited In (29)
- Set graphs. IV. Further connections with claw-freeness
- Covering codes of a graph associated with a finite vector space
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Locating sensors in paths and cycles: the case of 2-identifying codes
- Identifying codes and locating-dominating sets on paths and cycles
- Locating-dominating sets in local tournaments
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- An optimal locating-dominating set in the infinite triangular grid
- Locating-domination and identification
- On identification in the triangular grid
- Set graphs. II. Complexity of set graph recognition and similar problems
- Binary locating-dominating sets in rotationally-symmetric convex polytopes
- Identifying path covers in graphs
- Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
- Operads of finite posets
- Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code
- Identifying and locating-dominating codes on chains and cycles
- On the binary locating-domination number of regular and strongly-regular graphs
- Extremal Digraphs for open neighbourhood location-domination and identifying codes
- On the minimum size of an identifying code over all orientations of a graph
- Domination and location in twin-free digraphs
- Locating-dominating sets of functigraphs
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Locating-dominating sets in hypergraphs
- Identifying codes in line digraphs
- The binary locating-dominating number of some convex polytopes
- Approximability of identifying codes and locating-dominating codes
- Locating-dominating sets: from graphs to oriented graphs
- On locating--dominating sets in infinite grids
This page was built for publication: Identifying and locating-dominating codes: NP-completeness results for directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4677540)
