Adaptive Identification in GraphsRapport interne Télécom Paris-2007D012, Paris, France, 33 pages, septembre 2007.
Yael Ben-Haim*, Sylvain Gravier**, Antoine LOBSTEIN*** & Julien MONCEL****
* Department of Electrical Engineering-Systems
Tel Aviv University
Tel Aviv 69978, Israel
yael@eng.tau.ac.il
** Centre National de la Recherche Scientifique
Institut Fourier
100 rue des Maths, 38402 Saint Martin d'Hères, France
sylvain.gravier@ujf-grenoble.fr
*** Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
lobstein@enst.fr
**** INPG - Laboratoire Leibniz
46 avenue Félix Viallet, 38031 Grenoble Cedex, France
julien.moncel@imag.fr
Abstract. Consider a connected undirected graph G=(V,E), a subset C of vertices, and an integer r greater than or equal to 1; for any vertex v in V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v. We say that C is an r-identifying code of G if and only if all the sets Br(v) $\cap$ C are nonempty and pairwise distinct. These codes are used for devising location-detection schemes in wireless sensor networks. They were originally introduced to model a fault-detection problem in multiprocessor networks. By running a test procedure on all the processors corresponding to vertices of C, one can check if there is a faulty processor in the network, and locate the faulty processor if there is one.
In this paper we introduce an adaptive version of identifying codes, which enables one to run a test procedure on the processors of the network one after the other. We show a simple example where, in the worst case, adaptive identification requires a number of tests which is algorithmic in the minimum number of tests for the non-adaptive case. The purpose of this paper, after introducing adaptive identification in graphs and giving general bounds on adaptive r-identifying codes, is to study these codes in torii in the square and in the king lattices. We show that 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].