Subj : Splitting a tree quickly
To   : comp.programming,sci.math
From : Stephen White
Date : Sat Oct 08 2005 12:27 pm

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.

.