Construction of codes identifying sets of vertices (Q1773205): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:39, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Construction of codes identifying sets of vertices |
scientific article |
Statements
Construction of codes identifying sets of vertices (English)
0 references
25 April 2005
0 references
Summary: The problem of constructing graphs having a \((1,\leq \ell)\)-identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by \(\Omega(\frac{\ell^2}{\log\ell}\log n)\). Here we construct graphs on \(n\) vertices having a \((1,\leq\! \ell)\)-identifying code of cardinality \(O(\ell^4 \log n)\) for all \(\ell\! \geq 2\). We derive our construction from a connection between identifying codes and superimposed codes, which we describe in this paper.
0 references
identifying codes
0 references