McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at 
Web Address: