Balanced spanning tree (T) from undirected graph

9
votes

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.

3
algorithmgraphtree
Are the edges are equally weighted? If not, how should differing weights be handled? – Martin

3 Answers

2
votes

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.

0
votes

This appears to be trivial. Let G be your graph. It is connected, so there is an edge between each pair of vertices. Using the definition, construct an arbitrary balanced spanning tree G' with the same number of vertices as G. Starting at r in G' and an arbitrarily chosen vertex of G, map each vertex in G' to a vertex in G. Delete all edges in G that don't have a corresponding edge in G'.

The resulting graph -- call it U for "updated G" -- by construction has the same number of vertices as G', and further by construction, an edge exists in U iff the corresponding edge exists in G'. Thus U=G' and it follows that U is a balanced spanning tree.

-3
votes

You want to construct your tree as an AVL tree.

You can find additional information and code used to implement it starting on page 12 of this PDF document.

This PowerPoint document has some pretty pictures to help explain what's going on and also includes a Java implementation of the AVL Tree data type.