Degree-constrained spanning tree

Degree-constrained spanning tree

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k.

Formal definition

Input: n-node undirected graph G(V,E); positive integer kn.

Question: Does G have a spanning tree in which no node has degree greater than k?

NP-completeness

This problem is NP-complete. This can be shown by a reduction from the Hamiltonian path problem. It remains NP-complete even if k is fixed to a value ≥ 2. If you have defined that the degree must be ≤ k, the k = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

References

Search another word or see Degree-constrained spanning treeon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;