title: Divide-And-Conquer Algorithm for Trees
body: <p>I am trying to write a divide &amp; conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a <strong>node</strong>. All subgraphs should have the property that they don't contain more than <strong>n/2</strong> nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don't work:</p>
  
  <p><img src="https://i.stack.imgur.com/qNbko.png" alt="Graph"></p>
  
  <p>Is there some working algorithm that does what I want (returns the node H in the above case).</p>