19
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – David Eppstein Dec 20 '10 at 6:12
  • $\begingroup$ 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. $\endgroup$ – SuperElectric Dec 20 '10 at 6:20
  • $\begingroup$ Have you examined top trees? en.wikipedia.org/wiki/Top_tree $\endgroup$ – Peer Sommerlund Mar 14 '11 at 12:12
4
$\begingroup$

Every time you add a new vertex with an edge, you don't have options. Every time you add a new edge, if the current distance to the root is bigger than the distance through the new edge, you remove the old edge in the old shortest path and add the new one. Otherwise, you just keep your tree unchanged. I think this way you get something very similar to a BFS tree in the sense that the levels of the tree will contain the same vertices and the distance from a vertex to the root will be the same as the distance in the BFS tree (and in the graph), but I don't know if that's enough to satisfy your "ideal balanced spanning tree" condition.

$\endgroup$
2
$\begingroup$

I ended up doing the following:

Vinicius Santos' answer is the first part of it. As he says, at any frame I either add a new node and a parent-child edge connecting to it, or just add a cross-edge between two existing nodes. Parent-child edges offer no opportunities for changing the tree structure, only cross-edges do. Consider adding a cross-edge E between nodes A and B, where B has the greater tree depth. If (A.depth + 1) < B.depth, then we can lessen B.depth by making it a child of A.

Having lessened the depth of B, we now must check B's neighbors, to see if they may lessen their depth by becoming children of B. We therefore perform a breadth-first traversal from B, which traverses an edge from X to Y if X.depth+1 < Y.depth, and sets Y to be a child of X.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.