Q24

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 I := I ∪ {u} end; Output(I);