2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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 http://treegraph.bioinfweb.info/Help/wiki/Rerooting has a visual explanation of one technique.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – njvb
    Oct 9, 2011 at 20:18
  • $\begingroup$ 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. $\endgroup$ Oct 9, 2011 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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