Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice (Q882790)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice |
scientific article |
Statements
Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice (English)
0 references
24 May 2007
0 references
\textit{I. Honkala}, \textit{M. G. Karpovsky} and \textit{L. B. Levitin} [IEEE Trans. Inf. Theory 52, No. 2, 599--612 (2006)] introduced the concept of a \(t\)-edge-robust \(r\)-identifying code. This paper considers these codes in the king lattice and presents several optimal densities. In particular, the optimal densities for \(t\)-edge-robust \(1\)-identifying codes \((t\geq 1)\) in the king lattice have been presented. This result improves on the construction given by Honkala, Karpovsky and Levitin in which a \(1\)-edge-robust \(1\)-identifying code in the king lattice of density \(3/8\) was given. The code considered in the paper yields the density \(1/3\) which is optimal. It is also observed that while the density of a \(1\)-edge-robust \(r\)-identifying code can be made arbitrarily small by chosing \(r\) large enough, the density of a \(3\)-edge-robust \(r\)-identifying code is never less than \(1/2\).
0 references
\(t\)-edge-robust \(r\)-identifying codes
0 references
king lattice
0 references
optimal densities
0 references
graphs
0 references