Subj : Re: Splitting a tree quickly
To   : comp.programming
From : Lasse Kliemann
Date : Sun Oct 09 2005 02:13 am

Stephen White <mildredtoede@yahoo.com> wrote:
>
>       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?

For an edge e={v,w}, let n(e,v) be the number of vertices in the 
connected component of v in G-e, and n(e,w) the number of vertices in 
the connected component of w in G-e. The task is then to find an edge 
e={v,w} such that |n(e,v)-n(e,w)| is minimal. This is easy once we have 
all the n(.,.) values (just go over all edges; this takes O(n)).

These values should also be computable in O(n), using the recursion 
formula n(e,v) being the sum over all n(f,u), where f={v,u} ranges over 
all neighbors u of v, u not equal w, plus 1.

This solves the problem optimally.

.