| DATE: | Wednesday, October 1rst |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | Adjacency of optimal region of Huffman tree |
| SPEAKER: | Kensuke Onishi, Graduated School of Information systems, The University of Electro-Communications. |
Huffman tree and alphabetic tree have been studied data structures. For given keys' and weight these structures can be constructed easily. We deal with the space of weights. The space are divided into some regions such that at any point in the region a Huffman tree is optimal. Each region is called \textit{optimal region} of a Huffman tree.
In this talk we deal with these regions. Each region is convex, nonempty.
Two Huffman (alphabetic) trees are \textit{adjacent}
if there is a weight such that the only two trees under the weight
are optimal. We show that the necessary and sufficient condition of
adjacency is that the difference of level of each leaf is at most one and
the sum of two level vectors of trees is not equal to the sum of
any other two vectors.