Identifying and locating-dominating codes: NP-completeness results for directed graphs
From MaRDI portal
(Redirected from Publication:4677540)
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
Cited in
(30)- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Locating-dominating sets in hypergraphs
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- 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
- Sufficient conditions for a digraph to admit a (1, )-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
- Identifying path covers in graphs
- Set graphs. IV. Further connections with claw-freeness
- 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 codes and locating-dominating sets on paths and cycles
- On identifying vertices of tournament digraphs
- Domination and location in twin-free digraphs
- 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)
