Adaptive identification in Torii in the King lattice
type: Item
instance of: scholarly article
title: Adaptive identification in Torii in the King lattice
zbMATH Open document ID: 1217.05217
author: Yael Ben-Haim
author: Sylvain Gravier
author: Julien Moncel
author: Antoine Lobstein
published in: The Electronic Journal of Combinatorics
publication date: 2011-06-01T00:00:00Z
full work available at URL: https://eudml.org/doc/222848
full work available at URL: v18i1p116.html
review text: Summary: Given a connected graph \(G = (V, E)\), Let \(r \geq 1\) 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 N\)) if and only if all the sets \(Br(v) \cap C\) are nonempty and pairwise distinct. These codes were introduced previously 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ó.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94C12
zbMATH DE Number: 5903046
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5903046