Identifying Codes and Covering Problems

DOI10.1109/TIT.2008.928263zbMATH Open1318.94123OpenAlexW2132014457MaRDI QIDQ3604840FDOQ3604840

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

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.

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)

Cited In (16)

• Discriminating Codes in Geometric Setups
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• 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
• Generalized pentagonal geometries. II
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• 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)