-Alireza-'s blog

By -Alireza-, history, 4 weeks ago, In English

__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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints for this problem?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        I'm not sure!

        consider this example:

        http://s16.picofile.com/file/8411799542/Picture2.png

        0---0---0---0 (this is a graph)

        (I cant use images in comment)

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.