作者VSBSC (Trist)
看板Electronics
标题[问题]
时间Wed Jan 17 22:09:07 2007
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