-Alireza-'s blog

By -Alireza-, history, 4 weeks ago,

__hi! can somebody help me in this problem please? we have a graph and 2 type of reporters: 1 — can report the news to vertices with distance at most 1(from the reporter vertex) the price of this type is 1. 2 — can report to vertices with distance at most 2 . the price of this type is 2. what is the minimum total price to make sure that all vertices will receive the news.

for example in the graph above we can put a reporter of type 2 in the marked vertex and the total price will be 2.

I have a naive solution with O(3^n) time but that's not so good.

• 0

 » 4 weeks ago, # |   0 What are the constraints for this problem?
•  » » 4 weeks ago, # ^ |   0 that's not a contest or competition problem so it has no constraints. but I want something that support n <= 100 at least.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 If we just replace this problem with its' subproblem(how many reporters that cover distance 1 are needed), then this problem becomes the edge cover problem. I am no expert, but this might be a NP hard problem or a very challenging problem. Here is how you solve it for reporter that covers distance 1 only-Click
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I'm not sure!consider this example:http://s16.picofile.com/file/8411799542/Picture2.png0---0---0---0 (this is a graph)(I cant use images in comment)
•  » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 What I am trying to say is if we just consider its subproblem-how many reporters that cover distance 1 are needed-it becomes the edge cover problem. Look it up. If we have the reporter that cover distance 2 as well, then the problem might actually be NP hard or maybe solvable by modifying the solution of the edge-cover problem.