Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Adaptive Identification in Torii in the King Lattice. | Adaptive Identification in Torii in the King Lattice Yael Ben-Haim Sylvain Gravier f IBM Haifa Research Lab in Haifa Haifa University Campus Mount Carmel 31905 Haifa Israel yaelbh@ CNRS - Institut Fourier 100 rue des Maths - BP 74 38402 Saint Martin d Heres France Antoine Lobstein CNRS - LTCI UMR 5141 Institut Telecom - Telecom ParisTech 46 rue Barrault 75634 Paris Cedex 13 France lobstein@ Julien MonceC CNRS - LAAS Universite de Toulouse UPS INSA INP ISAE UT1 UTM LAAS 7 avenue du Colonel Roche 31077 Toulouse Cedex 4 France Submitted Apr 30 2011 Accepted May 13 2011 Published May 23 2011 Mathematics Subject Classification 05C99 05C70 94B60 94C12 Abstract Given a connected graph G V E Let r 1 be an integer and Br v denote the ball of radius r centered at v E V . the set of all vertices within distance r from v. A subset of vertices C c V is an r-identifying code of G for a given nonzero constant r E N if and only if all the sets Br v n C are nonempty and pairwise distinct. These codes were introduced in 7 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 Renyi-type search problem studied by M. Ruszinko 11 . Partially supported by ANR NSC Project GraTel ANR-09-blan-0373-01 and NSC99-2923-M-110-001-MY3 2010-2013 Partially supported by ANR Project IDEA ANR-08-EMER-007 .
