{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:50Z","timestamp":1740144530089,"version":"3.37.3"},"reference-count":17,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010253","name":"Secretar\u00eda de Ciencia y T\u00e9cnica, Universidad de Buenos Aires","doi-asserted-by":"publisher","award":["20020190100126BA"],"award-info":[{"award-number":["20020190100126BA"]}],"id":[{"id":"10.13039\/501100010253","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010253","name":"Secretar\u00eda de Ciencia y T\u00e9cnica, Universidad de Buenos Aires","doi-asserted-by":"publisher","award":["20020170100495BA"],"award-info":[{"award-number":["20020170100495BA"]}],"id":[{"id":"10.13039\/501100010253","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2022,5,6]]},"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:p>We study a special case of Hamming\u2013Huffman trees, in which both data compression and data error detection are tackled on the same structure. Given a hypercube<jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>of dimension<jats:italic>n<\/jats:italic>, we are interested in some aspects of its vertex neighborhoods. For a subset<jats:italic>L<\/jats:italic>of vertices of<jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, the neighborhood of<jats:italic>L<\/jats:italic>is defined as the union of the neighborhoods of the vertices of<jats:italic>L<\/jats:italic>. The minimum neighborhood problem is that of determining the minimum neighborhood cardinality over all those sets<jats:italic>L<\/jats:italic>. This is a well-known problem that has already been solved. Our interest lies in determining optimal Hamming\u2013Huffman trees, a problem that remains open and which is related to minimum neighborhoods in<jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. In this work, we consider a restricted version of Hamming\u2013Huffman trees, called [<jats:italic>k<\/jats:italic>]-HHT s, which admit symbol leaves in at most<jats:italic>k<\/jats:italic>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 .<\/jats:p>","DOI":"10.1051\/ro\/2022066","type":"journal-article","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T07:55:38Z","timestamp":1652255738000},"page":"1823-1839","source":"Crossref","is-referenced-by-count":0,"title":["Restricted Hamming\u2013Huffman trees"],"prefix":"10.1051","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5754-9761","authenticated-orcid":false,"given":"Min C.","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8498-2472","authenticated-orcid":false,"given":"Fabiano S.","family":"Oliveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7393-3464","authenticated-orcid":false,"given":"Paulo E. D.","family":"Pinto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-0753","authenticated-orcid":false,"suffix":"Jr.","given":"Moys\u00e9s S.","family":"Sampaio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,6,30]]},"reference":[{"key":"R1","first-page":"1","volume":"44","author":"Faria","year":"2016","journal-title":"Mat. Contemp."},{"key":"R2","unstructured":"Hamming R.W., Coding and Information Theory. Prentice-Hall (1986)."},{"key":"R3","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"Huffman","year":"1951","journal-title":"Proc. IRE"},{"key":"R4","first-page":"131","volume":"10","author":"Katona","year":"1977","journal-title":"Stud. Sci. Math. Hung."},{"key":"R5","unstructured":"Knuth D.E.. Art of Computer Programming. Vol. 1. Addison-Wesley (2005)."},{"key":"R6","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0012-365X(84)90068-2","volume":"51","author":"K\u00f6rner","year":"1984","journal-title":"Discrete Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(86)90047-6","volume":"62","author":"K\u00f6rner","year":"1986","journal-title":"Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Kruskal J.B., The number of simplices in a complex. In Mathematical Optimization Techniques, edited by Bellman R.. University of California Press (1963) 251\u2013278.","DOI":"10.1525\/9780520319875-014"},{"key":"R9","unstructured":"Pessoa A., An approximation algorithm for constructing error detecting prefix codes. Optimization Online (2006)."},{"key":"R10","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.ipl.2007.12.008","volume":"107","author":"Pessoa","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Pinto P.E.D., Protti F. and Szwarcfiter J.L., A Huffman-based error detecting code. In: Proc. of the Experimental and Efficient Algorithms (WEA\u20192004). Lecture Notes in Computer Science 3059 (2004) 446\u2013457.","DOI":"10.1007\/978-3-540-24838-5_33"},{"key":"R12","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1051\/ita:2005015","volume":"39","author":"Pinto","year":"2005","journal-title":"RAIRO \u2013 Theor. Inf. Appl."},{"key":"R13","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/978-3-642-02017-9_34","volume":"5532","author":"Pinto","year":"2009","journal-title":"Lect. Notes Comput. Sci."},{"key":"R14","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2012.03.047","volume":"440,441","author":"Pinto","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Wenisch T., Swaszek P.F. and Uht A.K., Combined error correction and compression codes. In: IEEE International Symposium on Information Theorys (2001) 238.","DOI":"10.1109\/ISIT.2001.936101"},{"key":"R16","unstructured":"Zipf G.K., Human Behaviour and the Principle of Least Effort. Addison-Wesley, (1949)."},{"key":"R17","unstructured":"https:\/\/github.com\/moysessj\/restricted-hamming-huffman-trees.git (Accessed: May 17, 2022)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022066\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T10:18:17Z","timestamp":1727173097000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5]]},"references-count":17,"journal-issue":{"issue":"3"},"alternative-id":["ro210431"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022066","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2022,5]]}}}