Identifying Codes and Covering Problems

DOI10.1109/TIT.2008.928263MaRDI QIDQ3604840zbMATH OpenOpenAlexFDO

Authors Moshe Laifenfeld, Ari Trachtenberg

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.2008.928263

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Recommendations

• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Approximability of identifying codes and locating-dominating codes
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.

Cited in

(16)

• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Discriminating Codes in Geometric Setups
• Identifying codes in hereditary classes of graphs and VC-dimension
• r-Identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube
• On robust and dynamic identifying codes
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Generalized pentagonal geometries. II
• Open locating-dominating sets in circulant graphs
• Identification in \(\mathbb Z^2\) using Euclidean balls
• Bounds on \(r\)-identifying codes in \(q\)-ary Lee space
• Constructions of \(r\)-identifying codes and \((r, \leq l)\)-identifying codes
• On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
• Improved upper bounds for identifying codes in n-dimensional q-ary cubes
• Complexity and approximation for discriminating and identifying code problems in geometric setups
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

This page was built for publication: Identifying Codes and Covering Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604840)