검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

The Huffman Tree Problem with Upper-Bounded Linear Functions 상한 선형 함수를 사용한 허프만 트리 문제

Hiroshi FUJIWARA, Yuichi SHIRAI, Hiroaki YAMAMOTO

  • 조회수

    0

  • 이것을 인용

요약 :

허프만 코드의 구성은 각 리프가 리프 깊이의 선형 함수와 연관되고 함수 값의 합이 최소화되는 완전 이진 트리를 찾는 문제로 이해될 수 있습니다. Fujiwara와 Jacobs는 이것을 일반적인 기능으로 확장하고 확장된 문제가 NP-난해함을 증명했습니다. 저자는 또한 나뭇잎과 관련된 함수가 각각 감소하지 않고 볼록함수가 다항식 시간에 해결 가능한 경우를 보여주었습니다. 그러나 감소하지 않는 비볼록 함수의 경우의 복잡성은 아직 알려지지 않았습니다. 본 논문에서는 선형 함수나 상수 중 더 작은 값을 취하는 비감소 비볼록 함수를 고려하여 복잡성을 밝히려고 합니다. 결과적으로 우리는 그러한 함수의 두 하위 클래스에 대한 다항식 시간 알고리즘을 제공합니다.

발행
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.474-480
발행일
2022/03/01
공개일
2021/10/12
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2021FCP0006
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
범주

작성자

Hiroshi FUJIWARA
  Shinshu University
Yuichi SHIRAI
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

키워드