Balanced spanning tree (T) from undirected graph

Question

I have connected undirected graph. I am looking for the way to construct the balanced spanning tree (T) of a graph

The specific about balanced spanning tree, I could define as follows:

1. If the root of the tree is r .All nodes could be divided to the levels.I.e all the nodes which distance from the r (in T) is j are in the level Lj,etc.
2. For each node w one can define for a sub-tree T_w of T,such that w is its root.
3. The goal is to define spanning tree in such a way that for each level Li,for every two nodes u and v in level Li the number of nodes in the T_u and T_v is maximally equivalent.

Does anybody can advice any algorithm/s for building such “relatively” balanced spanning tree?

Thank you in advance.

Answer 1

I am not sure about your expression "maximally equivalent."

This problem may not have a perfect solution, so the obvious thing is how much better can we do?

This problem in generality seems to be NP-Complete. Some greedy approaches might result in constant approx algorithms, if you are lucky.