Minimum degree spanning tree

In graph theory, for a connected graph $G$ , a spanning tree $T$ is a subgraph of $G$ with the least number of edges that still spans $G$ . A number of properties can be proved about $T$ . $T$ is acyclic, has ( $|V|-1$ ) edges where $V$ is the number of vertices in $G$ etc.

A minimum degree spanning tree $T'$ is a spanning tree which has the least maximum degree. The vertex of maximum degree in $T'$ is the least among all possible spanning trees of $G$ .

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 is issued from Wikipedia - version of the 6/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.