Subj : Re: Splitting a tree quickly
To   : comp.programming,sci.math
From : klewis
Date : Sun Oct 09 2005 04:17 am

"Stephen White" <mildredtoede@yahoo.com> writes in article <1128796054.147969.90280@g49g2000cwa.googlegroups.com> dated 8 Oct 2005 11:27:34 -0700:
>
>      Is there a simple way to quickly split a tree (in the graph
>theoretical sense) roughly in half by removing an edge?
>      So the actual work is finding the appropriate edge.
>      Specifically, could you find an edge such that the parts of the
>tree on either side of the edge each have at most 2n/3 vertices (where
>n is the number of nodes in the original tree)?  Could this be done in
>O(n) or at least O(n log n) time?  If this is infeasible, what about if
>we tolerated at most (2n+4)/3 vertices on either side?

Traversing a tree is O(n).  Counting nodes during the traversal and keeping
track of the closest number to n/2 is the same, if you assume addition and
subtraction are O(1).  

However, there are pathological cases where you cannot get anywhere near
n/2.  For example, the 100-node tree with the first node having 99 edges and
the other nodes all being leaves, so removal of any single edge would split
the tree into 99+1.

In summary, you can do a best fit algorithm within your time constraints but
you cannot guarantee that the best fit will be good.

--Keith Lewis              klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.

.