An exact algorithm for k-cardinality degree constrained clustered minimum spanning tree problem

The k-cardinality degree constrained clustered minimum spanning tree problem (k-DCCMST) aims to determine a k-node (out of n nodes) spanning tree of minimum weight defined on a complete weighted undirected graph, where the node set is partitioned into set of clusters such that except the root node, the degree of other nodes in the resultant spanning tree does not exceed the predefined degree limit. The k-DCCMST model has significant applications in the context of designing of networks and is then formulated as a zero-one integer linear program. To solve this problem optimally, an exact Lexi-search algorithm (LSA) is developed. The developed LSA is subjected in Matlab, tested on some benchmark as well as randomly generated test instances and computational results are reported. Numerical experimental results demonstrate the efficiency of proposed LSA on dense graphs. (paper)