MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a graph $G(V,E)$ and a tree $T(V',E')$ where $|V|=|V'|$ and $T$ is isomorphic to a subgraph of $G$. In other words I found a spanning tree of $G$ and made one of its nodes act as the root.

I now have 2 problems I want to look at:

  1. If I remove a node from $G$ what is the optimal way to determine if a new $T$ exits and if so find it. 2.Assume $v_0$ is the root of $T$. I'm given an arbitrary node $v_i$ and need to find a new $T$ in which $v_i$ is the root.

I would like to know what (if any) literature or solutions already exist for these problems?

I am asking this question because I am working on a project involving network topologies and would like to know about any existing solution (especially if they have proofs) before I start trying to solve the problem on my own.

share|cite|improve this question
up vote 4 down vote accepted

I think the following paper will probably answer your first question

Henzinger, M., & Valerie, K. (1997). Maintaining minimum spanning trees in dynamic graphs. Automata, Languages and Programming, 1256, 594-604. Doi: 10.1007/3-540-63165-8_214

The answer to your second question can be found in several places. The page at has a visual explanation of one technique.

share|cite|improve this answer
The paper does seem to be what I'm looking for (haven't read past the intro yet) but the rerooting link is not. they assume that nodes are being deleted from the tree, however in my case no nodes are being removed the root is simply being switched to a different node requiring a restructuring of who is a parent node and who is a child node. – user14534 Oct 9 '11 at 20:18
The case where the existing root is not being deleted is straightforward: simply reverse the parent-child relationship between the new node and its extant parent. The new root and the old root cannot share any descendants, because then there would have been a cycle in the tree. In the directed case, add a path from $v_i$ to $v_o$ to $T$, remove the link from the parent of $v_i$ to $v_i$ and break any cycles created. – Chad Musick Oct 9 '11 at 20:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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