Revision as of 19:01, 13 July 2007 edit Michael Hardy (talk \| contribs) Administrators 210,577 edits m moved Degree constrained spanning tree to Degree-constrained spanning tree ← Previous edit		Revision as of 23:31, 24 July 2007 edit undo Michael Hardy (talk \| contribs) Administrators 210,577 edits m →NP-completeness Next edit →
Line 12: ==NP-completeness== This problem is [[NP-Complete]]. This can be shown by a reduction from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥  2. If you have defined that the degree must be <= ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem. ==References==

Degree-constrained spanning tree: Difference between revisions