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 k ≤ n.

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

NP-completeness

This problem is NP-complete (Garey & Johnson 1979). 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 the problem is defined as the degree must be ≤ k, the k = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

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.[1]

Heuristic algorithms that can solve the problem in polynomial time have been proposed, including Genetic and Ant-Based Algorithms.

Approximation Algorithm

Fürer & Raghavachari (1994) gave an approximation algorithm for the problem which, on any given instance, either shows that the instance has no tree of maximum degree k or it finds and returns a tree of maximum degree k+1.

References

  1. ↑ Bui, T. N. and Zrncic, C. M. 2006. An ant-based algorithm for finding degree-constrained minimum spanning tree. In GECCO ’06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 11–18, New York, NY, USA. ACM.
This article is issued from Wikipedia - version of the Friday, March 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.