Algorithm for smallest subtree having all of a set of nodes (subtrees)
in [Logic]
|
Prev: Why the Ignorant / Stupid Are the First Responders to Good Math / Science / Tech OPs
Next: BP loves Waxman-Obama cap&trade (circa Kyoto Protocol, or Waxman's '91 bill)
From: Charlie-Boo on 22 Jun 2010 15:36 What is the smallest subtree of a given tree that has all of a given set of nodes within it? C-B
From: Chip Eastham on 22 Jun 2010 21:50 On Jun 22, 3:36 pm, Charlie-Boo <shymath...(a)gmail.com> wrote: > What is the smallest subtree of a given tree that has all of a given > set of nodes within it? > > C-B Since a tree lacks cycles, but is connected, isn't it evident that any pair of nodes has a unique connecting path? Take the union of paths connecting pairs of distinct nodes in the given set. Such a thing is clearly connected, and cycle-free, so... I suppose it remains to sweat out details for the case of a single node. regards, chip
From: Rob Pratt on 22 Jun 2010 15:58
"Charlie-Boo" <shymathguy(a)gmail.com> wrote in message news:aba6cd56-1ed6-4733-8b4f-d30812b1b27e(a)u7g2000yqm.googlegroups.com... > What is the smallest subtree of a given tree that has all of a given > set of nodes within it? > > C-B http://mathworld.wolfram.com/SteinerTree.html |