An independent set in a graph is a subset of vertices such that no two…

PYQ GATE 1994

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);

(a) Complete the algorithm by specifying the property of vertex u in each case

(b) What is the time complexity of the algorithm.

Attempted by 1 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…