The Degree-constrained Minimum K-tree Problem

We consider the degree-constrained minimum K-tree problem,which is a generaliza-tion of the degree-constrained minimum tree problem and the minimum K-tree problem.The problem is defined as follows:given an undirected weighted graph G =(V,E;?,K),where ?:E? R0+,|V| = n + 1 and a positive integer K,S = {vi1,vi2,...,vis}(?)V and a pair of positive integers aik,bik(aik ? bik)for each vertex vik ? S.We are asked to find a K-tree T,such that aik?dT(vik)? bik for each vertex vik ? S,the objective is to minimize the sum of weight of the T,i.e.w(T)= min{?e?T'?(e)| T' is a K-tree of G,aik ? dT(vik)? bik,(?)vik ? S}.We obtain two results as follows:(1)when S is not an independent set,we prove that the problem is NP-complete;(2)when S is an independent set,we design a polynomial-time algorithm,with time complexity 0(n4)to slove it.