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

(17)

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

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)