\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Yael Ben-Haim, Sylvain Gravier, Antoine Lobstein and Julien Moncel}
%
%
\medskip
\noindent
%
%
{\bf Adaptive Identification in Torii in the King Lattice}
%
%
\vskip 5mm
\noindent
%
%
%
%
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, {\em On
a New Class of Codes for Identifying Vertices in Graphs\/}, IEEE
Transactions on Information Theory \textbf{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 \textit{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\'enyi-type search problem studied by M.~Ruszink\'o [M.~Ruszink\'o,
{\em On a 2-dimensional Search Problem,} Journal of Statistical
Planning and Inference {\bf 37(3)} (1993), 371--383].
\end{document}