Adaptive identification in graphs (Q958720): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Antoine C. Lobstein / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sharad S. Sane / rank | |||
Normal rank |
Revision as of 03:31, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Adaptive identification in graphs |
scientific article |
Statements
Adaptive identification in graphs (English)
0 references
8 December 2008
0 references
Let \(G\) be a given (undirected and connected) graph and let \(r\) denote a positive integer. A code \(C\) is a subset of vertices of \(G\) and vertices in \(C\) are called the codewords. \(C\) is called an \(r\)-covering code if for any vertex \(v\) of \(G\), the ball of radius \(r\) centered at \(v\) has at least one codeword. and \(C\) is called an \(r\)-packing if the \(r\)-balls centered at the codewords are disjoint. \(C\) is called an \(r\)-identifying code if \(\forall v \neq v'\) in \(V = V(G)\), the sets \(C \cap B_r(v)\) and \(C \cap B_r(v')\) are distinct (here \(B_r(x)\) means the ball of radius \(r\) centered at \(x\)). This paper introduces an adaptive version of identifying codes. These codes are motivated by various engineering applications. Bounds on adaptive identifying codes are given for regular graphs and torii in the square grid. The new codes.are compared to the classical non-adaptive case.
0 references
Codes
0 references
covering
0 references
packing
0 references
identifying
0 references
adaptive
0 references