One way of trying to avoid this dependence on ordering is the use of randomized algorithms. Essentially, by processing the vertices in a random order, you can potentially avoid (with high probability) any particularly bad orderings. So consider the following randomized algorithm for constructing independent sets: @ First, starting with an empty set I, add each vertex of G to I independently with probability p. @ Next, for any edges with both vertices in I, delete one of the two vertices from I (at random). @ Note - in this second step, deleting one vertex from I may remove multiple edges from I! @vReturn the final set I. 4) Argue that the output of this algorithm is an independent set. Is it 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.
One way of trying to avoid this dependence on ordering is the use of randomized algorithms. Essentially, by processing
the vertices in a random order, you can potentially avoid (with high probability) any particularly bad orderings. So
consider the following randomized
@ First, starting with an empty set I, add each vertex of G to I independently with probability p.
@ Next, for any edges with both vertices in I, delete one of the two vertices from I (at random).
@ Note - in this second step, deleting one vertex from I may remove multiple edges from I!
@vReturn the final set I.
4) Argue that the output of this algorithm is an independent set. Is it a maximal independent set?
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
