Adaptive Identification in GraphsJournal of Combinatorial Theory, Ser. A, Vol. 115, pp. 1114-1126, 2008.
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. An adaptive version of identifying codes is introduced. These codes are motivated by various engineering applications. Bounds on adaptive identifying codes are given for regular graphs and torii in the square grid. The new codes are compared to the classical non-adaptive case.