Artículo
Restricted Hamming-Huffman Trees
Lin, Min Chih
; de Souza Oliveira, Fabiano; Pinto, Paulo E. D.; Sampaio, Moysés S.; Szwarcfiter, Jayme L.
Fecha de publicación:
06/2022
Editorial:
EDP Sciences
Revista:
RAIRO - Operations Research
ISSN:
2804-7303
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
We study a special case of HammingHuffman trees, in which both data compression and data error detection are tackled on the same structure. Given a hypercube Qn of dimension n, we are interested in some aspects of its vertex neighborhoods. For a subset L of vertices of Qn, the neighborhood of L is defined as the union of the neighborhoods of the vertices of L. The minimum neighborhood problem is that of determining the minimum neighborhood cardinality over all those sets L. This is a well-known problem that has already been solved. Our interest lies in determining optimal HammingHuffman trees, a problem that remains open and which is related to minimum neighborhoods in Qn. In this work, we consider a restricted version of HammingHuffman trees, called [k]-HHT s, which admit symbol leaves in at most k different levels. We present an algorithm to build optimal [2]-HHT s. For uniform frequencies, we prove that an optimal HHT is always a [5]-HHT and that there exists an optimal HHT which is a [4]-HHT. Also, considering experimental results, we conjecture that there exists an optimal tree which is a [3]-HHT.
Palabras clave:
HAMMINGHUFFMAN CODES
,
HYPERCUBE GRAPHS
,
MINIMUM NEIGHBORHOOD
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos (IC)
Articulos de INSTITUTO DE CALCULO
Articulos de INSTITUTO DE CALCULO
Citación
Lin, Min Chih; de Souza Oliveira, Fabiano; Pinto, Paulo E. D.; Sampaio, Moysés S.; Szwarcfiter, Jayme L.; Restricted Hamming-Huffman Trees; EDP Sciences; RAIRO - Operations Research; 56; 3; 6-2022; 1823-1839
Compartir
Altmétricas