7. (15 points) Given an undirected graph G- (V,E) and a positive weight w, for e

Question

7. (15 points) Given an undirected graph G- (V,E) and a positive weight w, for each vertex i in V, a subset of vertices C is called "stable" if no two vertices in C are connected with an edge in E. The weight of a subset of vertices C is the sum of the individual weights of the vertices in C. The maximum weight stable set problem is to find a stable set of maximum weight. Design a heuristic solution to find a feasible solution for any instance of the problem s O In particular, for the above graph, c-(3,4) is a stable set of weight 10 and C (2,4,5) is the maximum weight stable set of weight 12. Apply your greedy heuristic to the above instance

Explanation / Answer

We answer this question with a step by step algorithm:

Step.1 Write down all stable subsets of the given graph and index them as C1, C2 and so on

Step.2 For each Ci compute the weight as sum of all the individual weights.

Step.3 The maximum over all Ci is the required answer.

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.