In:
RAIRO - Operations Research, EDP Sciences, Vol. 56, No. 3 ( 2022-05), p. 1823-1839
Kurzfassung:
We study a special case of Hamming–Huffman trees, in which both data compression and data error detection are tackled on the same structure. Given a hypercube Q n of dimension n , we are interested in some aspects of its vertex neighborhoods. For a subset L of vertices of Q n , 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 Hamming–Huffman trees, a problem that remains open and which is related to minimum neighborhoods in Q n . In this work, we consider a restricted version of Hamming–Huffman trees, called [ k ]-HHT s, which ad mit 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 .
Materialart:
Online-Ressource
ISSN:
0399-0559
,
2804-7303
Sprache:
Englisch
Verlag:
EDP Sciences
Publikationsdatum:
2022
ZDB Id:
1468388-X
SSG:
3,2
Bookmarklink
