We are given a social network as an undirected graph where vertices are people a

Question

We are given a social network as an undirected graph where vertices are people and edges represent friendship between them on our network. A "cover" is a subset S of people (vertices) such that everyone not in the set S is friends with someone in S We use the following greedy algorithm to find the smallest size cover S possible While the graph is not empty: Select the node n in the graph which has the maximum number of friends (incident edges). Add n to the set S Delete n and all its friends from the graph.

Explanation / Answer

A. Smallest cover will be 2,3,4,5 or 1,2,3,4

B. By greedy algorithm the cover will be 5,6,7,8,9,10

C. It chooses a cover, but may not be the minimal cover

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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