I think that you can solve it using dynamic programming. For instance,
let d[u] = the weight of the subtree rooted at u. Then d[u] =
weight[u] + sum_{v is a child of u} d[v]. Now it's your turn to think
about how to prove you can compute d[u] for all u as efficiently as
possible (e.g., can you fin
Those two results hold for the max mean weight subtree problem, don't
they?
On Jan 29, 4:27 am, LazyBoy <[EMAIL PROTECTED]> wrote:
> You can find some of the answers in this paperhttp://arxiv.org/pdf/cs/0503023
>
> Some of the results given are:
> - A linear-time algorithm to solve the problem
ld);
> return max( (max(R,L,R+L)+root.value), R, L, root.value );
>
> }
> -Original Message-
> From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
>
> Behalf Of Debajit Adhikary
> Sent: Tuesday, January 29, 2008 12:40 PM
> To: Algorithm Gee
ld);
> return max( (max(R,L,R+L)+root.value), R, L, root.value );
>
> }
> -Original Message-
> From: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] On
>
> Behalf Of Debajit Adhikary
> Sent: Tuesday, January 29, 2008 12:40 PM
> To: Algorithm Gee
y, January 29, 2008 12:40 PM
> To: Algorithm Geeks
> Subject: [algogeeks] Re: Finding the subtree with the largest weight
>
> > On Jan 29, 2008 3:07 PM, Debajit Adhikary <[EMAIL PROTECTED]> wrote:
>
> > > Lets say I have a weighted tree (with positive, zero and negative
&g
2:40 PM
> To: Algorithm Geeks
> Subject: [algogeeks] Re: Finding the subtree with the largest weight
>
> > On Jan 29, 2008 3:07 PM, Debajit Adhikary <[EMAIL PROTECTED]> wrote:
>
> > > Lets say I have a weighted tree (with positive, zero and negative
> > > weig
Behalf Of Debajit Adhikary
Sent: Tuesday, January 29, 2008 12:40 PM
To: Algorithm Geeks
Subject: [algogeeks] Re: Finding the subtree with the largest weight
> On Jan 29, 2008 3:07 PM, Debajit Adhikary <[EMAIL PROTECTED]> wrote:
>
> > Lets say I have a weighted tree (with positive,
You can find some of the answers in this paper
http://arxiv.org/pdf/cs/0503023
Some of the results given are:
- A linear-time algorithm to solve the problem with positive weights
- A proof of NP-Completeness when negative weights are allowed
On Jan 29, 2:09 pm, Debajit Adhikary <[EMAIL PROTE
> On Jan 29, 2008 3:07 PM, Debajit Adhikary <[EMAIL PROTECTED]> wrote:
>
> > Lets say I have a weighted tree (with positive, zero and negative
> > weights for each node).
> > How could I best find the subtree having the maximum weight?
On Jan 29, 3:55 am, "Yingjie Xu" <[EMAIL PROTECTED]> wrote:
>
A rooted tree or a general tree?
On Jan 29, 2008 3:07 PM, Debajit Adhikary <[EMAIL PROTECTED]> wrote:
>
> Lets say I have a weighted tree (with positive, zero and negative
> weights for each node).
> How could I best find the subtree having the maximum weight?
> >
>
--~--~-~--~~-
10 matches
Mail list logo
