Geodesic
Construction of codes identifying sets of vertices
The electronic journal of combinatorics, Tome 12 (2005)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
In this paper the problem of constructing graphs having a $(1,\le \ell)$-identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by $\Omega\left({\ell^2\over\log \ell}\log n\right)$. Here we construct graphs on $n$ vertices having a $(1,\le \ell)$-identifying code of cardinality $O\left(\ell^4 \log n\right)$ for all $\ell \ge 2$. We derive our construction from a connection between identifying codes and superimposed codes, which we describe in this paper.
DOI : 10.37236/1910
Classification : 05C99, 94B60, 94C12
Mots-clés : identifying codes 
Sylvain Gravier; Julien Moncel. Construction of codes identifying sets of vertices. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1910
@article{10_37236_1910,
     author = {Sylvain Gravier and Julien Moncel},
     title = {Construction of codes identifying sets of vertices},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1910},
     zbl = {1060.05091},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1910/}
}
TY  - JOUR
AU  - Sylvain Gravier
AU  - Julien Moncel
TI  - Construction of codes identifying sets of vertices
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1910/
DO  - 10.37236/1910
ID  - 10_37236_1910
ER  - 
%0 Journal Article
%A Sylvain Gravier
%A Julien Moncel
%T Construction of codes identifying sets of vertices
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1910/
%R 10.37236/1910
%F 10_37236_1910

Cité par Sources :