On the size of identifying codes in binary hypercubes
From MaRDI portal
Publication:1024996
DOI10.1016/J.JCTA.2009.02.004zbMATH Open1173.94009arXiv0804.3029OpenAlexW2135472198MaRDI QIDQ1024996FDOQ1024996
Authors: Svante Janson, Tero Laihonen 
Publication date: 18 June 2009
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let C be a subset of F^n. For any subset X of F^n, denote by I_r(X)=I_r(C;X) the set of elements of C within distance r from at least one x in X. Now C is called an (r,<= l)-identifying code if the sets I_r(X) are distinct for all subsets X of size at most l. We estimate the smallest size of such codes with fixed l and r/n converging to some number rho in (0,1). We further show the existence of such a code of size O(n^{3/2}) for every fixed l and r slightly less than n/2, and give for l=2 an explicit construction of small such codes for r the integer part of n/2-1 (the largest possible value).
Full work available at URL: https://arxiv.org/abs/0804.3029
Recommendations
- Identifying codes in \(q\)-ary hypercubes
- Publication:4502621
- On the density of identifying codes in the square lattice
- New bounds on binary identifying codes
- On identifying codes in binary Hamming spaces
- Monotonicity of the minimum cardinality of an identifying code in the hypercube
- Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes
- Upper bounds for binary identifying codes
- On binary linear \(r\)-identifying codes
- scientific article; zbMATH DE number 1522566
Cites Work
- On a new class of codes for identifying vertices in graphs
- On identifying codes in binary Hamming spaces
- Title not available (Why is that?)
- Monotonicity of the minimum cardinality of an identifying code in the hypercube
- Structural properties of twin-free graphs
- On codes identifying sets of vertices in Hamming spaces
- Codes identifying sets of vertices in random networks
- Extremal cardinalities for identifying and locating-dominating codes in graphs
- Identifying codes of cycles
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Exact Minimum Density of Codes Identifying Vertices in the Square Grid
- Title not available (Why is that?)
- Improved bounds on identifying codes in binary Hamming spaces
- Locating sensors in paths and cycles: the case of 2-identifying codes
- New bounds on binary identifying codes
Cited In (19)
- New bounds for contagious sets
- On identifying codes in binary Hamming spaces
- Improved bounds on identifying codes in binary Hamming spaces
- New identifying codes in the binary Hamming space
- On the size of identifying codes in triangle-free graphs
- Identifying codes and searching with balls in graphs
- Locating vertices using codes
- On Iiro Honkala's contributions to identifying codes
- New bounds on binary identifying codes
- Open locating-dominating sets in circulant graphs
- Identifying codes in \(q\)-ary hypercubes
- Identifying codes in the direct product of a complete graph and some special graphs
- Identifying codes of the direct product of two cliques
- Identifying codes of corona product graphs
- Locating-Domination and Identification
- Optimal identifying codes of two families of Cayley graphs
- On minimum identifying codes in some Cartesian product graphs
- Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes
- Huge Size Codes for Identification Via a Multiple Access Channel Under a Word-Length Constraint
This page was built for publication: On the size of identifying codes in binary hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024996)
