About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Electronic Journal of Combinatorics
Paper
Adaptive identification in torii in the king lattice
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 ∈ V, i.e., the set of all vertices within distance r from v. A subset of vertices C ⊆ V is an r-identifying code of G (for a given nonzero constant r ∈ N) if and only if all the sets Br(v) ∩ 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 Rényi-type search problem studied by M. Ruszinkó [11].