Improved bounds on identifying codes in binary Hamming spaces
type: Item
instance of: scholarly article
title: Improved bounds on identifying codes in binary Hamming spaces
zbMATH Open document ID: 1196.94094
author: Geoffrey Exoo
author: Ville Junnila
author: Tero Laihonen
author: Sanna Ranto
published in: European Journal of Combinatorics
publication date: 2010-04-27T00:00:00Z
review text: Consider the set \(\mathbb{F}^n\) of binary vectors of length \(n\). Let \(X\) be a subset of \(\mathbb{F}^n\). The \textit{ball \(B_r(X)\) of radius \(r\) } around \(X\) is the set of all binary vectors of length \(n\) that are at Hamming distance at most \(r\) from at least one element of \(X\). A code \(C\subset \mathbb{F}^n\) is called \textit{\((r,\leq l)\)-identifying} if for all \(X,Y\subseteq \mathbb{F}^n\) such that \(|X|,|Y|\leq l\) and \(X\neq Y\), the sets \(B_r(X)\cap C\) and \(B_r(Y)\cap C\) are different. Identifying codes were first introduced by \textit{M. G. Karpovsky, K. Chakrabarty} and \textit{L. B. Levitin} [IEEE Trans. Inform. Theory 44 (2), 599--561 (1998; Zbl 1105.94342)]. They are used to find malfunctioning processors in multiprocessor systems, and they are also used in sensor networks. In both applications, the goal is to find identifying codes, as small as possible. This article improves lower bounds on \((r,\leq 1)\)-identifying codes for \(r>1\). Then, new lower bounds on \((r,\leq l)\)-identifying codes with \(l\geq 2\) are presented. Two methods constructing \((r,\leq l)\)-identifying codes from known other \((r,\leq l)\)-identifying codes also are given.
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 5702076
zbMATH Keywords: identifying codes
reviewed by: Leo Storme
MaRDI profile type: Publication
full work available at URL: j.ejc.2009.09.002
OpenAlex ID: W2037219199
cites work: Exact Minimum Density of Codes Identifying Vertices in the Square Grid
cites work: Q4948746
cites work: Bounds on identifying codes
cites work: New identifying codes in the binary Hamming space
cites work: A linear algorithm for minimum 1-identifying codes in oriented trees
cites work: Q4342497
cites work: Improved Upper Bounds on Binary Identifying Codes
cites work: New bounds on binary identifying codes
cites work: Codes identifying sets of vertices in random networks
cites work: Q4329059
cites work: Identifying codes of cycles
cites work: Q4510800
cites work: On robust and dynamic identifying codes
cites work: On a new class of codes for identifying vertices in graphs
cites work: Sequences of optimal identifying codes
cites work: Extremal cardinalities for identifying and locating-dominating codes in graphs
cites work: Monotonicity of the minimum cardinality of an identifying code in the hypercube
cites work: Fault-tolerant locating-dominating sets
DOI: 10.1016/J.EJC.2009.09.002
Recommended article: New bounds on binary identifying codes
Recommended article: On the size of identifying codes in binary hypercubes
Recommended article: On binary linear \(r\)-identifying codes
Recommended article: Optimal linear identifying codes
Recommended article: On codes identifying sets of vertices in Hamming spaces
Recommended article: New identifying codes in the binary Hamming space
Recommended article: Bounds on identifying codes
Recommended article: Upper bounds for binary identifying codes
Recommended article: Q4502621
Recommended article: Two families of optimal identifying codes in binary Hamming spaces
description: scientific article; zbMATH DE number 5702076