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.



Tree graph restructuring.
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.


