Degree-constrained spanning tree: Difference between revisions

Revision as of 17:02, 15 September 2011

Revision as of 08:03, 12 July 2012

Line 12:

==Degree-constrained minimum spanning tree==

On a weighted graph, a Degree-constrained minimum spanning tree (DCMST) is a degree-constrained spanning tree in withwhich the sum of its verticesedges has the minimum 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>