On identifying codes
From MaRDI portal
An \(r\)-identifying code in a general graph is a set \(C\) of vertices such that the balls \(B_r(v)\) of radius \(r\) contain a different (not necessarily disjoint) set of elements in \(C\) for each vertex \(v\). The authors show that no perfect \(r\)-identifying code exists for \(r>1\) using a certain concept of perfect code, give an improved lower bound on the density of codes on square lattices, and show the existence of such 1-identifying codes is NP-complete.NEWLINENEWLINEFor the entire collection see [Zbl 0960.00079].
Recommendations
Cited in
(51)- On identifying codes in the hexagonal mesh
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
- The minimum density of an identifying code in the king lattice.
- Optimal codes for strong identification
- Localization game on geometric and planar graphs
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- On identification in the triangular grid
- On the density of identifying codes in the square lattice
- Optimal identifying codes in cycles and paths
- New results of identifying codes in product graphs
- Set graphs. II. Complexity of set graph recognition and similar problems
- Identifying codes of degree 4 Cayley graphs over abelian groups
- Approximability of identifying codes and locating-dominating codes
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- On cages admitting identifying codes
- Extremal graphs for the identifying code problem
- 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
- More results on the complexity of identifying problems in graphs
- Codes for strong identification
- Edge identifying codes
- Locating-domination and identification
- Discriminating codes in bipartite graphs
- scientific article; zbMATH DE number 5555992 (Why is no real title available?)
- scientific article; zbMATH DE number 1504659 (Why is no real title available?)
- On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
- Code Reverse Engineering Problem for Identification Codes
- scientific article; zbMATH DE number 7655282 (Why is no real title available?)
- (r,k)-catching code
- Identifying codes in some subgraphs of the square lattice
- Some rainbow problems in graphs have complexity equivalent to satisfiability problems
- Identifying codes for generalized quadrangles
- Progress on fault-tolerant locating-dominating sets
- Identification in \(\mathbb Z^2\) using Euclidean balls
- Identifying codes and locating-dominating sets on paths and cycles
- Density of identifying codes of hexagonal grids with finite number of rows
- On Iiro Honkala's contributions to identifying codes
- Optimal local identifying and local locating-dominating codes
- Fault-tolerant locating-dominating sets on the infinite tumbling block graph
- Optimal error-detection system for identifying codes
- Fault-tolerant locating-dominating sets with error-correction
- Fault-tolerant identifying codes in special classes of graphs
- Error-correcting open-locating-dominating sets
- Combinatorial identification problems and graph powers
- On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
- On a new class of identifying codes in graphs
- On robust identification in the square and King grids
- Discriminating codes in (bipartite) planar graphs
This page was built for publication: On identifying codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2717197)
