The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.474-480

- Publication Date
- 2022/03/01

- Publicized
- 2021/10/12

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2021FCP0006

- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)

- Category

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.

Copy

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

Copy

@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},}

Copy

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 -