Consider an undirected graph G = (V;E). An independent set is a subset I V such that for any vertices i; j 2 I, there is no edge between i and j in E. A set i is a maximal independent set if no additional vertices of V can be added to I without violating its independence. Note, however, that a maximal independent sent is not necessarily the largest independent set in G. Let (G) denote the size of the largest maximal independent set in G. Consider the following greedy algorithm for generating maximal independent sets: starting with an empty set I, process the vertices in V one at a time, adding v to I is v is not connected to any vertex already in I. 2) Argue that the output I of this algorithm is a maximal independent set.
Consider an undirected graph G = (V;E). An independent set is a subset I V such that for any vertices i; j 2 I,
there is no edge between i and j in E. A set i is a maximal independent set if no additional vertices of V can be
added to I without violating its independence. Note, however, that a maximal independent sent is not necessarily
the largest independent set in G. Let (G) denote the size of the largest maximal independent set in G.
Consider the following greedy
process the vertices in V one at a time, adding v to I is v is not connected to any vertex already in I.
2) Argue that the output I of this algorithm is a maximal independent set.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images