User - MathOverflow

Tree graph restructuring.

2011-10-09T00:27:26Z

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:

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.

FO complexity class

2011-04-20T00:21:10Z

I'm currently in a theory of computing class and as such I have been looking up information about P vs NP and other complexity classes out of curiosity. In the process I cam across a blog post discussing a recent "proof" (it turned out to be wrong of course) of P not equal NP and in it they discussed the FO(LFP) complexity class.

Now I've understood all complexity classes so far, but even after reading to Wikipedia, and complexity zoo entries on FO and first order logic I still don't understand this complexity class at all. I have come to the understanding that FO is the set of all algorithms or problems (correct me if I'm wrong) that can be solved using first order logic which somehow avoids entering the realm of algorithmics. The problem is I don't understand what the first order part of first order logic means or how algorithms are represented as such.

Now Wikipedia simply defined it as being not higher order logic which was pretty vegue. I have a good understanding of boolean logic and some understanding of logic in general, but I have the feeling that due to all the special notation that is used in the explanations I read I am not seeing the forest for the trees. Can someone explain to me what property of first order logic makes it different from other kinds of logic and give an example of how this can represent an algorithm?

Comment by

2011-10-09T20:18:13Z

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.

Comment by

2011-04-20T02:25:08Z

Is that better or do I need to be more specific?