Adaptive identification in graphs
type: Item
instance of: scholarly article
title: Adaptive identification in graphs
zbMATH Open document ID: 1183.94063
author: Yael Ben-Haim
author: Sylvain Gravier
author: Julien Moncel
author: Antoine Lobstein
published in: Journal of Combinatorial Theory. Series A
publication date: 2008-12-08T00:00:00Z
review text: Let \(G\) be a given (undirected and connected) graph and let \(r\) denote a positive integer. A code \(C\) is a subset of vertices of \(G\) and vertices in \(C\) are called the codewords. \(C\) is called an \(r\)-covering code if for any vertex \(v\) of \(G\), the ball of radius \(r\) centered at \(v\) has at least one codeword. and \(C\) is called an \(r\)-packing if the \(r\)-balls centered at the codewords are disjoint. \(C\) is called an \(r\)-identifying code if \(\forall v \neq v'\) in \(V = V(G)\), the sets \(C \cap B_r(v)\) and \(C \cap B_r(v')\) are distinct (here \(B_r(x)\) means the ball of radius \(r\) centered at \(x\)). This paper introduces an adaptive version of identifying codes. 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.
Mathematics Subject Classification ID: 94B99
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 5379244
zbMATH Keywords: Codes
zbMATH Keywords: covering
zbMATH Keywords: packing
zbMATH Keywords: identifying
zbMATH Keywords: adaptive
reviewed by: Sharad Sane
MaRDI profile type: Publication
full work available at URL: j.jcta.2007.12.009
OpenAlex ID: W2092469145
cites work: Exact Minimum Density of Codes Identifying Vertices in the Square Grid
cites work: Q4948746
cites work: General bounds for identifying codes in some infinite regular graphs
cites work: The minimum density of an identifying code in the king lattice.
cites work: Identifying codes with small radius in some infinite regular graphs
cites work: Q4342497
cites work: Q5556894
cites work: Perfect Codes in the Lee Metric and the Packing of Polyominoes
cites work: Construction of codes identifying sets of vertices
cites work: On identification in the triangular grid
cites work: On the identification of sets of points in the square lattice
cites work: On codes identifying sets of vertices in Hamming spaces
cites work: On identifying codes in binary Hamming spaces
cites work: On a new class of codes for identifying vertices in graphs
cites work: Q4474243
cites work: On a 2-dimensional search problem
DOI: 10.1016/J.JCTA.2007.12.009
Recommended article: Q5403016
Recommended article: Adaptive aggregation on graphs
Recommended article: Q5396723
Recommended article: Graph signatures: identification and optimization
Recommended article: A graph theoretical approach to the parameters identifiability characterisation
Recommended article: Adaptive estimation of nonparametric geometric graphs
Recommended article: An optimal lower bound on the number of variables for graph identification
description: scientific article; zbMATH DE number 5379244