most recent 30 from http://mathoverflow.net 2013-05-25T22:22:44Z http://mathoverflow.net/feeds/question/77569 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77569/tree-graph-restructuring njwizz 2011-10-09T00:27:26Z 2011-10-09T01:19:58Z

<p>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.</p> <p>I now have 2 problems I want to look at:</p> <ol> <li>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.</li> </ol> <p>I would like to know what (if any) literature or solutions already exist for these problems? </p> <p>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.</p>

http://mathoverflow.net/questions/77569/tree-graph-restructuring/77572#77572 Chad Musick 2011-10-09T01:19:58Z 2011-10-09T01:19:58Z

<p>I think the following paper will probably answer your first question</p> <p>Henzinger, M., &amp; Valerie, K. (1997). Maintaining minimum spanning trees in dynamic graphs. <i>Automata, Languages and Programming, 1256</i>, 594-604. Doi: 10.1007/3-540-63165-8_214</p> <p>The answer to your second question can be found in several places. The page at <a href="http://treegraph.bioinfweb.info/Help/wiki/Rerooting" rel="nofollow">http://treegraph.bioinfweb.info/Help/wiki/Rerooting</a> has a visual explanation of one technique.</p>