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.