WEKO3
アイテム
On the Huffman and Alphabetic Tree Problem with General Cost Functions
http://hdl.handle.net/10091/00020329
http://hdl.handle.net/10091/00020329eee66cb6-778e-4fc3-8dd1-0afca02ae484
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
On_the_Huffman_and_Alphabetic_Tree_Problem_with_General_Cost_Functions.pdf (150.9 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2018-03-09 | |||||
| タイトル | ||||||
| タイトル | On the Huffman and Alphabetic Tree Problem with General Cost Functions | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| DOI | ||||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | https://doi.org/10.1007/s00453-013-9755-6 | |||||
| 関連名称 | 10.1007/s00453-013-9755-6 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Optimal tree | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Binary tree | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Multi-ary tree | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Dynamic programming | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Huffman coding | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Alphabetic tree | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Fujiwara, Hiroshi
× Fujiwara, Hiroshi× Jacobs, Tobias |
|||||
| 信州大学研究者総覧へのリンク | ||||||
| 表示名 | Fujiwara, Hiroshi | |||||
| URL | http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html | |||||
| 出版者 | ||||||
| 出版者 | SPRINGER | |||||
| 引用 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | ALGORITHMICA. 69(3): 582-604 (2014) | |||||
| 書誌情報 |
ALGORITHMICA 巻 69, 号 3, p. 582-604, 発行日 2014 |
|||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i, instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O(n (4)) optimal algorithm using space O(n (3)). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a "monotonicity" property can be applied. For the generalized Huffman Tree Problem we show that even the k-ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA'90, pp. 310-318, 1990) when the cost functions are nondecreasing and convex. Furthermore, we give an O(n (2)logn) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent. | |||||
| 資源タイプ（コンテンツの種類） | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | Article | |||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0178-4617 | |||||
| 権利 | ||||||
| 権利情報 | The original publication is available at www.springerlink.com | |||||
| 出版タイプ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| WoS | ||||||
| 表示名 | Web of Science | |||||
| URL | http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000335752000005 | |||||
