On identifying codes (Q2717197)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On identifying codes |
scientific article; zbMATH DE number 1604774
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On identifying codes |
scientific article; zbMATH DE number 1604774 |
Statements
18 September 2001
0 references
identifying code
0 references
square lattice
0 references
NP-complete
0 references
On identifying codes (English)
0 references
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].
0 references
