AnotherRound's blog

By AnotherRound, history, 7 years ago, In English

The steiner tree problem can be formulated this way:

We have a weighted connected graph (V, E) and a subset of its vertices(let's say it is Q). We have to find a subtree of this graph that has minimal weight and contains Q. Now, this is a "famous" NP problem, but I thought what if the graph was unweighted, or alternatively all edges have the same weight? Is this problem easier or has the same complexity?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it