ISI2011-PCB-CS-3c

Question

A vertex cover of a graph $G = (V, E)$ is a set of vertices $V' \subseteq V$ such that for any edge $(u, v) \in E$, either $u$ or $v$\ (or both) is in $V'$. Write a linear time algorithm to find the minimum vertex cover of a given tree $T$. Establish its correctness.

Answer 1

Do a tree traversal(preorder,post order or inorder)

Count the number of non leaf nodes

O(n) time.

Answer 2

@Jothee. You would write a loop like

for(i=0; i<E; i++)

So, its basically linear in terms of index of 'E' i.e T(n)=O(E)  but E=O(V²) so this is inherently quadratic running time algo.