Hey @DanielFischer
I want to write an algorithm that finds an optimal vertex cover of a tree in linear time O(n), where n is the number of the vertices of the tree..
I have tried the following:
http://pastebin.com/8PUhynhd
Its time complexity is $T(n)=\sum_{i=1}^{|V|} O(|V_i|+|E_i|) \leq \sum_{i=1}^{|V|} O(|E_i|) \leq \sum O(|E|)=O(|V| \cdot |E|)$.
($|V_i|, |E_i|$ are the number of vertices and edges respectively of the subtrees at the root of which we call DFS )
Right? Or have I calulated the time complexity wrong?
I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2)
A simple cycle is a path in a graph that starts and ends at the same vertex without passing through the same ...
