There are n neighborhoods in Indiana. You are given a map where neighborhoods ar

Question

There are n neighborhoods in Indiana. You are given a map where neighborhoods are vertices and adjacent neighborhoods are connected by an edge (Each neighborhood has at least one adjacent neighborhood.). Suppose we would like to open some stores in Indiana, so that everyone can either go to a store in his/her neighborhood, or a store in an adjacent neighborhood. However due to budget problems we can only open at most n/2 stores. 1. Design an algorithm that finds at most ln/2 neighborhoods, such that if those ne borhoods have a store, everyone can find a store either in their neighborhood or in at

Explanation / Answer

1) Case 1: Assume the given graph is connected

Algorithm_Connected()

1) Find minimum vertex cover ,Vi

2) Select the n/2 vertices from the set Vi which have the maximum degree .

Note : Vertex cover for wheel graph generally results in a upper bound of (n+2)/2 and for complete graph n-1. But this problem is covered by the step 2.

The given problem is not existing in case of an odd cycle graph. So that case is not considered.

Case 2: The graph is disconnected

Algorithm_disconnected()

1: Find Each component of graph

2: For each component run the Algorithm_Connected()

3: For each vertex coverings select subset of size,K

4: If the union of selected subsets results in the solution then terminate the process

5: else repeat the step 4 with different subsets or different K

2) This given solution cover the sub problem of vertex covering. Which is HP- Hard. Therefore the given solution is not optimal.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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