The One Vertex Degree-constrained K-tree Construction Problem

The degree-constrained K-tree problem is a classical problem in algorithm graph theory,which has significant practical application value and theoretical re-search value.In this paper,we consider the degree-constrained K-tree construction problem,which is the generalization of the degree-constrained tree construction problem and the minimum K-tree problem.The problem is defined as follows:give a weighted graph G“pV,E;wq,where w:E?R<sup>`</sup>,one fixed vertices v<sub>0</sub>P V,one non-negative integer K and one positive integers d,we are asked to construct a degree-constrained K-tree T<sub>K</sub>“pV,E<sub>K</sub>q,e P E<sub>K</sub>,satisfying d<sub>T</sub> pv<sub>0</sub>q“d.These n`K edges are assembled from some stock pieces of bounded length L.Let c₀be the sale price of each stock piece of length L,kpT_Kq the number of minimum stock pieces,cpeq be the construction cost of that edge e.The objec-tive is to minimize the total cost of constructing a degree-constrained K-tree T_K,i.e.mint?_ePEKcpeq`kpT_Kq¨c₀u.In this paper,In the construction,two cases of construction cost are consid-ered.In the first case,when considering the construction cost,we designed the DCKTC algorithm to solve the k-tree construction problem limiting a vertex de-gree.It is a 2-approximation algorithm,whose complexity is Opn³q.In the second case,when the construction cost is 0,we designed the DCKTP algorithm to solve the k-tree construction problem that restricts a vertex degree,whose complexity is Opn³q.Based on DCKTC algorithm theory,on the MATLAB language pro-gramming,the program consists of four parts,respectively is DCKTC algorithm is the main program and Prim algorithm,Frisher algorithm and ChangeDegree algorithm.