Subj : Re: Splitting a tree quickly
To   : comp.programming,sci.math
From : Michael Schneider
Date : Sun Oct 09 2005 02:00 am

What is the representation of the Tree?

What do you use to determine tree order?

Can you control these?

Mike

Stephen White wrote:
> Hello,
> 
>       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?
> 
>      Thanks for any help you can offer.
> 


-- 
The greatest performance improvement occurs on the transition of from 
the non-working state to the working state.

.