Author |
Topic: optimal merging tree (Read 1622 times) |
|
cuckoo
Junior Member
Gender: 
Posts: 57
|
 |
optimal merging tree
« on: Dec 7th, 2011, 7:00pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: optimal merging tree
« Reply #1 on: Dec 9th, 2011, 2:41am » |
Quote Modify
|
So, are we given the leaf nodes with weights? and we need to create the internal nodes? Is that right?
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
cuckoo
Junior Member
Gender:
Posts: 57
|
|
Re: optimal merging tree
« Reply #2 on: Dec 9th, 2011, 3:15am » |
Quote Modify
|
Yes, the weights of leaf-nodes are pre-defined.
The tree is in any form with n leaf-nodes.
on Dec 9th, 2011, 2:41am, TenaliRaman wrote:So, are we given the leaf nodes with weights? and we need to create the internal nodes? Is that right?
-- AI |
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print