Minimum degree spanning tree
In graph theory, for a connected graph , a spanning tree is a subgraph of with the least number of edges that still spans . A number of properties can be proved about . is acyclic, has () edges where is the number of vertices in etc.
A minimum degree spanning tree is a spanning tree which has the least maximum degree. The vertex of maximum degree in is the least among all possible spanning trees of .
Finding minimum degree spanning tree is NP hard, but a local search algorithm can give a tree which its maximum degree is at most the maximum degree of optimal tree plus one.
See Degree-Constrained Spanning Tree.
![]() | This article does not cite any sources. (April 2009) |
Categories:
- Spanning tree