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)
“The whole tree itself is but one leaf, and rivers are still vaster leaves whose pulp is intervening earth, and towns and cities are the ova of insects in their axils.”
—Henry David Thoreau (1817–1862)