Geodesic
Adaptive identification in Torii in the King lattice
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a connected graph $G=(V,E)$, Let $r\geq1$ be an integer and $B_r(v)$ denote the ball of radius $r$ centered at $v\in V$, i.e., the set of all vertices within distance $r$ from $v$. A subset of vertices $C \subseteq V$ is an $r$-identifying code of $G$ (for a given nonzero constant $r\in \mathbb{N}$) if and only if all the sets $B_r(v)\cap C$ are nonempty and pairwise distinct. These codes were introduced in [M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a New Class of Codes for Identifying Vertices in Graphs, IEEE Transactions on Information Theory 44(2) (1998), 599–611] to model a fault-detection problem in multiprocessor systems. They are also used to devise location-detection schemes in the framework of wireless sensor networks. These codes enable one to locate a malfunctioning device in these networks, provided one scans all the vertices of the code. We study here an adaptive version of identifying codes, which enables to perform tests dynamically. The main feature of such codes is that they may require significantly fewer tests, compared to usual static identifying codes. In this paper we study adaptive identifying codes in torii in the king lattice. In this framework, adaptive identification can be closely related to a Rényi-type search problem studied by M. Ruszinkó [M. Ruszinkó, On a 2-dimensional Search Problem, Journal of Statistical Planning and Inference 37(3) (1993), 371–383].
DOI : 10.37236/603
Classification : 05C99, 05C70, 94B60, 94C12 
@article{10_37236_603,
     author = {Yael Ben-Haim and Sylvain Gravier and Antoine Lobstein and Julien Moncel},
     title = {Adaptive identification in {Torii} in the {King} lattice},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/603},
     zbl = {1217.05217},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/603/}
}
TY  - JOUR
AU  - Yael Ben-Haim
AU  - Sylvain Gravier
AU  - Antoine Lobstein
AU  - Julien Moncel
TI  - Adaptive identification in Torii in the King lattice
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/603/
DO  - 10.37236/603
ID  - 10_37236_603
ER  - 
%0 Journal Article
%A Yael Ben-Haim
%A Sylvain Gravier
%A Antoine Lobstein
%A Julien Moncel
%T Adaptive identification in Torii in the King lattice
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/603/
%R 10.37236/603
%F 10_37236_603
Yael Ben-Haim; Sylvain Gravier; Antoine Lobstein; Julien Moncel. Adaptive identification in Torii in the King lattice. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/603

Cité par Sources :