Degree-constrained spanning tree: Difference between revisions

Revision as of 23:32, 24 July 2007

Revision as of 02:45, 4 November 2008

Line 1:

{{Expand|date=January 2007}}

{{Cleanup|date=December 2006}}

Line 12 ⟶ 11:

==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==