摘要：This paper deals with the degree constrained k-cardinality minimum spanning tree (k-MSTPD) problem defined on a connected, edge weighted and undirected graph. The aim of this problem is to determine the least weighted spanning tree with exactly k vertices such that except the root vertex, no other vertex in the resultant spanning tree exceeds the specified degree limit. The k-MSTPD problem has many practical applications for the design of electric, communication, and transportation networks. The problem is then formulated as a zero-one programming. In this paper, an exact algorithm known as Lexi-search algorithm (LSA) is developed to tackle the k-MSTPD problem. Furthermore, the developed LSA is programmed in Matlab and tested on some benchmark instances as well as on random instances and the respective results are reported. The obtained experimental results showed that the developed LSA takes significantly less time to find the optimal solutions.
