Algorithms

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy
algorithm to find a maximum independent set in a tree is given below:

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I); 

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.