[Math] Algorithm of tree partition

algorithmsgraph theory

I am looking for algorithm which allows to do following:

Let $T$ is some tree, where each vertex $V_i$ has its cost $c_i$. I am looking for algorithm which allows to split $T$ (by removing two edges) to three connected components $S_i$ with equal sum of costs of vertices

Best Answer

Wouldn't something like this base algorithm work?

  1. Collect all leafs
  2. For all nodes connected with a leaf, create a new leaf with the sum of the leafs and the node.
  3. Once it exceeds 1/3 of the total, cut it off as a tree.

There will be special cases, and you may need to throw in some tree balancing when there are large differences in weights of the leafs/nodes.