Content deleted Content added
→Degree-constrained minimun spanning tree: fixing link |
|||
Line 11:
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
On a weighted graph, a Degree-constrained minimun spanning tree (DCMST) is a degree-constrained spanning tree in with the sum of its vertices has the minimun possible sum. Finding a DCMST is an NP-Hard problem.<ref>Bui, T. N. and Zrncic, C. M. 2006. [http://www.cs.york.ac.uk/rts/docs/GECCO_2006/docs/p11.pdf An ant-based algorithm for finding degree-constrained minimum spanning tree.]
In GECCO ’06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 11–18, New York, NY, USA. ACM.</ref>
| |||