The Two Fixed Vertices Degree-constrained Minimum K-tree Problem

The degree-constrained K-tree problem is a class of combinatorial optimization problems. It has very important theoretical research value and actual application value. We consider a generalization of the degree-constrained K-tree problem, i.e. the two vertices-fixed degree-constrained minimum K-tree problem, it can be difined as follows:given a weighted graph G=(V,E;w), where w:E Eâ†'R+, two fixed vertices vS,vt∈V and two positive integers k1,k2, and a non-negative integer K, we are asked to find a degree-constrained minimum K-tree TKst with two vertices-fixed satisfying dTKst(vs)=k1and dTKst(vt)=k2, the objective is to minimize the weight of K-tree TKst.In this thesis, we design a polynomial-time algorithm to solve the two vertices-fixed degree-constrained minimum K-tree problem, its complexity is O(n4); As well as compiling the MATLAB programming for the algorithm and the example of algorithm is realized.