An approximate algorithm for degree constraint minimum spanning tree

DCMST (Degree Constraint Minimum Spanning Tree) is a special case of minimum spanning tree problem which is concerned with finding a spanning tree of a nonnegative edge weighted graph such that all nodes satisfy degree restrictions and total edge length is minimum. It is an important problem in operation research and finds application in communication network design where degree of a node is indicator of input-output ports available on that terminal. As it is NP-complete problem so in this paper we design an approximate algorithm which works in three stages and determines a spanning tree satisfying degree constraint and also guarantees to give nearly optimal tree with respect to cost.