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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Chad Musick
    Commented Oct 9, 2011 at 20:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .