Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Is the steiner tree on unweighted graph also NP-hard?

Правка en1, от AnotherRound, 2017-08-10 10:32:26

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?

Теги graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AnotherRound 2017-08-10 10:32:26 463 Initial revision (published)