# maintaining a balanced spanning tree of a growing undirected graph

I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.

I have an undirected graph that starts as a single node, the "root".

At each step, I add to the graph either a new node and an edge connecting it to the graph, or just a new edge, connecting two old nodes. As I grow the graph, I maintain a spanning tree. Most of the time, this means that when I add a new node and edge, I set the new node to be the child of the old node that it connects to.

I have no control over the order in which the new nodes are added, so the above tree-building algorithm can obviously lead to imbalanced spanning trees.

Does anybody know of online heuristics that will keep the spanning tree "relatively balanced", while minimizing the amount of work done in re-treeing? I have full control over the tree structure. What I don't control is the graph connectivity, or the order in which new nodes are added.

Note that the standard Google responses to terms like "balanced" "spanning" and "tree" seem to be binary trees and B-trees, neither of which apply. My graph nodes can have any number of neighbors, so the tree nodes can have any number of children, not 2 like binary trees. B-trees maintain balance by changing their adjacency lists, and I cannot change the graph connectivity.

• Maybe it would help if you were more specific about what your ideal balanced spanning tree of a static graph would be. Is a BFS tree automatically a good choice as a balanced tree (it's as shallow as possible, if you choose the right root, or within a factor of two regardless of root)? Do you need the number of nodes in each subtree to be smaller by a constant factor than the number of nodes at the parent, everywhere in the tree, and if so what do you do for graphs that don't have such trees? Dec 20, 2010 at 6:12
• A BFS tree would indeed be an ideal balanced spanning tree if I were running this offline, with the entire graph given at once. There's no need for the number of nodes in each subtree to be smaller by a constant factor than the number of nodes in the parent. Dec 20, 2010 at 6:20
• Have you examined top trees? en.wikipedia.org/wiki/Top_tree Mar 14, 2011 at 12:12