2004年
Adjacency of optimal regions for Huffman trees
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- 巻
- 3106
- 号
- 開始ページ
- 13
- 終了ページ
- 22
- 記述言語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/978-3-540-27798-9_4
- 出版者・発行元
- Springer
The Huffman tree is a binary tree storing each leaf with a key and its weight with the smallest weighted search time (i.e., the weighted sum of external path lengths). The combinatorial structure of the Huffman tree depends on the weights of keys, and thus the space of weights is tessellated into regions called optimal regions associated with the combinatorial structures. In this paper we investigate properties of this tessellation. We show that each optimal region is convex and non-empty. Moreover, we give a combinatorial necessary and sufficient condition for the adjacency of optimal regions. We also give analogous results for alphabetic trees. © Springer-Verlag Berlin Heidelberg 2004.
- リンク情報
-
- DOI
- https://doi.org/10.1007/978-3-540-27798-9_4
- DBLP
- https://dblp.uni-trier.de/rec/conf/cocoon/Onishi04
- URL
- https://dblp.uni-trier.de/conf/cocoon/2004
- URL
- https://dblp.uni-trier.de/db/conf/cocoon/cocoon2004.html#Onishi04
- Scopus
- https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=35048864023&origin=inward
- Scopus Citedby
- https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=35048864023&origin=inward
- ID情報
-
- DOI : 10.1007/978-3-540-27798-9_4
- ISSN : 0302-9743
- eISSN : 1611-3349
- DBLP ID : conf/cocoon/Onishi04
- SCOPUS ID : 35048864023