wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> optimal merging tree
        
(Message started by: cuckoo on Dec 7^th, 2011, 7:00pm)

Title: optimal merging tree
Post by cuckoo on Dec 7^th, 2011, 7:00pm

Let T be a tree with n leaf nodes. Each node of the tree has a weight. The weight of each leaf node is w_i (1 \le i \le n), and the weight of an internal node is the sum of the weights of its child nodes.

How to construct an optimal tree such that \sum w(v)*d(v) is minimized?

Notations: w(v) is the weight of node v, and d(v) is the out-degree of node v.

Title: Re: optimal merging tree
Post by TenaliRaman on Dec 9^th, 2011, 2:41am

So, are we given the leaf nodes with weights? and we need to create the internal nodes? Is that right?

-- AI

Title: Re: optimal merging tree
Post by cuckoo on Dec 9^th, 2011, 3:15am

Yes, the weights of leaf-nodes are pre-defined.
The tree is in any form with n leaf-nodes.

on 12/09/11 at 02:41:36, TenaliRaman wrote:

So, are we given the leaf nodes with weights? and we need to create the internal nodes? Is that right?

-- AI