On the complexity of the identification problem in Hamming spaces

DOI10.1007/S00236-002-0093-4MaRDI QIDQ1403334zbMATH OpenOpenAlexFDO

Authors Iiro Honkala, Antoine Lobstein

Publication date 1 September 2003

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-002-0093-4

zbMATH Keywords

Hamming distance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05)

Recommendations

• On identifying codes in binary Hamming spaces
• Improved bounds on identifying codes in binary Hamming spaces
• On a conjecture regarding identification in Hamming graphs
• Links Between Discriminating and Identifying Codes in the Binary Hamming Space
• New identifying codes in the binary Hamming space
• Two families of optimal identifying codes in binary Hamming spaces
• On codes identifying sets of vertices in Hamming spaces
• The communication complexity of the Hamming distance problem
• On the complexity of recognizing Hamming graphs and related classes of graphs
• Recognizing Hamming graphs in linear time and space

Cited in

(12)

• On identification in the triangular grid
• More results on the complexity of identifying problems in graphs
• Identification Rate, Search and Memory Complexity Tradeoff: Fundamental Limits
• Locating-domination and identification
• Witness Sets
• \(r\)-identifying codes in binary Hamming space, \(q\)-ary Lee space and incomplete hypercube
• Bounds on r-identifying codes in q-ary Lee space
• On the Efficiency of the Hamming C-Centerstring Problems
• Links Between Discriminating and Identifying Codes in the Binary Hamming Space
• On Iiro Honkala's contributions to identifying codes
• On identifying codes in binary Hamming spaces
• New identifying codes in the binary Hamming space

This page was built for publication: On the complexity of the identification problem in Hamming spaces

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