The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
허프만 코드의 구성은 각 리프가 리프 깊이의 선형 함수와 연관되고 함수 값의 합이 최소화되는 완전 이진 트리를 찾는 문제로 이해될 수 있습니다. Fujiwara와 Jacobs는 이것을 일반적인 기능으로 확장하고 확장된 문제가 NP-난해함을 증명했습니다. 저자는 또한 나뭇잎과 관련된 함수가 각각 감소하지 않고 볼록함수가 다항식 시간에 해결 가능한 경우를 보여주었습니다. 그러나 감소하지 않는 비볼록 함수의 경우의 복잡성은 아직 알려지지 않았습니다. 본 논문에서는 선형 함수나 상수 중 더 작은 값을 취하는 비감소 비볼록 함수를 고려하여 복잡성을 밝히려고 합니다. 결과적으로 우리는 그러한 함수의 두 하위 클래스에 대한 다항식 시간 알고리즘을 제공합니다.
Hiroshi FUJIWARA
Shinshu University
Yuichi SHIRAI
Shinshu University
Hiroaki YAMAMOTO
Shinshu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Hiroshi FUJIWARA, Yuichi SHIRAI, Hiroaki YAMAMOTO, "The Huffman Tree Problem with Upper-Bounded Linear Functions" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 474-480, March 2022, doi: 10.1587/transinf.2021FCP0006.
Abstract: The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0006/_p
부
@ARTICLE{e105-d_3_474,
author={Hiroshi FUJIWARA, Yuichi SHIRAI, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={The Huffman Tree Problem with Upper-Bounded Linear Functions},
year={2022},
volume={E105-D},
number={3},
pages={474-480},
abstract={The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.},
keywords={},
doi={10.1587/transinf.2021FCP0006},
ISSN={1745-1361},
month={March},}
부
TY - JOUR
TI - The Huffman Tree Problem with Upper-Bounded Linear Functions
T2 - IEICE TRANSACTIONS on Information
SP - 474
EP - 480
AU - Hiroshi FUJIWARA
AU - Yuichi SHIRAI
AU - Hiroaki YAMAMOTO
PY - 2022
DO - 10.1587/transinf.2021FCP0006
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.
ER -