Degree-constrained spanning tree: Difference between revisions

Revision as of 02:07, 19 October 2010

Revision as of 02:13, 19 October 2010

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-constrained minimun spanning tree==

On a weighted graph, a Degree Constrained-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.unm.edu/~tnguyen/Papers/mc.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>

Heuristic algorithms that can solve the problem in polinomial time have been proposed, including Genetic Algorithm and Ant-Based Algorithms.

==Approximation Algorithm==