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 freeLoading lesson…

