On identifying codes in binary Hamming spaces
From MaRDI portal
This paper studies the asymptotic minimum sizes \(M_r(n)\) of binary \(r\)-identifying codes \(C\subset \{ 0,1\}^n\). That means that all the sets \(B_r(x)\cap C\) are nonempty and distinct. The result is \[ \lim_{n\to \infty} n^{-1}M_{\lfloor \rho n \rfloor} (n) =1+\rho \log_2 \rho +(1-\rho) \log_2 (1-\rho). \] For linear codes, it is shown that the problem of determining whether a given code is \(r\)-identifying is \(\Pi_2\)-complete by reducing a \(\forall \exists \) 3-dimensional matching problem to it.
Recommendations
Cites work
- A nonconstructive upper bound on covering radius
- Balancing sets of vectors
- Bounds on identifying codes
- Do most binary linear codes achieve the Goblick bound on the covering radius? (Corresp.)
- Families of optimal codes for strong identification
- Good coverings of Hamming spaces with spheres
- scientific article; zbMATH DE number 3763833 (Why is no real title available?)
- scientific article; zbMATH DE number 107798 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1024657 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1522566 (Why is no real title available?)
- scientific article; zbMATH DE number 1436153 (Why is no real title available?)
- Linear codes with covering radius 2 and other new covering codes
- On a new class of codes for identifying vertices in graphs
- On codes identifying sets of vertices in Hamming spaces
- On strongly identifying codes
- On the complexity of the identification problem in Hamming spaces
- On tilings of the binary vector space
- Optimal codes for strong identification
- Sequences of optimal identifying codes
- The complexity of computing the covering radius of a code
- Two families of optimal identifying codes in binary Hamming spaces
- Unit sphere packings and coverings of the Hamming space
Cited in
(32)- Upper bounds for binary identifying codes
- On the size of identifying codes in binary hypercubes
- On the complexity of the identification problem in Hamming spaces
- Identifying codes in the direct product of a complete graph and some special graphs
- On identification in the triangular grid
- Locating and identifying codes in dihedral graphs
- Optimal identifying codes of two families of Cayley graphs
- Improved upper bounds for identifying codes in n-dimensional q-ary cubes
- New results of identifying codes in product graphs
- On t-revealing codes in binary Hamming spaces
- On two variations of identifying codes
- On identifying codes that are robust against edge changes
- On minimum identifying codes in some Cartesian product graphs
- Sphere coverings and identifying codes
- Identifying codes of the direct product of two cliques
- Locating and identifying codes in circulant networks
- Identifying codes of corona product graphs
- Monotonicity of the minimum cardinality of an identifying code in the hypercube
- More results on the complexity of identifying problems in graphs
- Locating-domination and identification
- scientific article; zbMATH DE number 1522566 (Why is no real title available?)
- \(r\)-identifying codes in binary Hamming space, \(q\)-ary Lee space and incomplete hypercube
- Links Between Discriminating and Identifying Codes in the Binary Hamming Space
- On binary linear \(r\)-identifying codes
- scientific article; zbMATH DE number 5228468 (Why is no real title available?)
- On Iiro Honkala's contributions to identifying codes
- Identifying codes in the direct product of a path and a complete graph
- A family of optimal identifying codes in \(\mathbb Z^2\)
- Identifying codes in vertex-transitive graphs and strongly regular graphs
- New bounds on binary identifying codes
- Adaptive identification in graphs
- New identifying codes in the binary Hamming space
This page was built for publication: On identifying codes in binary Hamming spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696908)
