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:
“After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.”
—Barbara Ehrenreich (20th century)
“A tree there is that from its topmost bough
Is half all glittering flame and half all green
Abounding foliage moistened with the dew;
And half is half and yet is all the scene;
And half and half consume what they renew....”
—William Butler Yeats (1865–1939)