[問題]
Steiner tree problem:
given a graph G=(V,E), and some of vertices marked, find the minimum subtree
of
G that contains the marked vertices? the steiner tree problem is even
NP-compl\
ete
if all weight of each edge is equivalent.
Steiner tree 如何從 Ham. Path reduce 證明為 NP-complete problem??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.144.93
討論串 (同標題文章)