Degree-constrained spanning tree: Difference between revisions

Revision as of 15:42, 3 February 2025

Latest revision as of 19:27, 6 February 2025

Line 10:

==NP-completeness==

This problem is [[NP-complete]] {{harv|Garey|Johnson|1979}}. This can be shown by a [[Reduction (complexity)|reduction]] from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

This problem is [[NP-complete]] {{harv|Garey|Johnson|1979}}. 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 the problem is defined as the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

==Degree-constrained minimum spanning tree==