Talk:K-minimum spanning tree
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Untitled
[edit]I think this page can be replaced by the "steiner tree" page, or at the very least ought to refer to the steiner tree page and explain why this is different. — Preceding unsigned comment added by 213.199.128.156 (talk) 14:47, 9 September 2008 (UTC)
I believe the steiner tree problem is different, as in that case the set of vertices to include is given to start with, while in this problem we are only given the number of vertices to be included. The text should probably be modified to clarify that. Also, strictly speaking it is the associated decision problem (is there one with weight less than some number?) that is NP-complete, not the problem of finding such a k-minimum spanning tree. Satyr9 (talk) 19:33, 10 February 2009 (UTC)