Degree-constrained Minimum Spanning Tree
On a weighted graph, a Degree-constrained minimum spanning tree (DCMST) is a degree-constrained spanning tree in which the sum of its edges has the minimum possible sum. Finding a DCMST is an NP-Hard problem.
Heuristic algorithms that can solve the problem in polynomial time have been proposed, including Genetic and Ant-Based Algorithms.
Read more about this topic: Degree-constrained Spanning Tree
Famous quotes containing the words minimum and/or tree:
“There are ... two minimum conditions necessary and sufficient for the existence of a legal system. On the one hand those rules of behavior which are valid according to the system’s ultimate criteria of validity must be generally obeyed, and on the other hand, its rules of recognition specifying the criteria of legal validity and its rules of change and adjudication must be effectively accepted as common public standards of official behavior by its officials.”
—H.L.A. (Herbert Lionel Adolphus)
“But when the bowels of the earth were sought,
And men her golden entrails did espy,
This mischief then into the world was brought,
This framed the mint which coined our misery.
...
And thus began th’exordium of our woes,
The fatal dumb-show of our misery;
Here sprang the tree on which our mischief grows,
The dreary subject of world’s tragedy.”
—Michael Drayton (1563–1631)