To search, Click below search items.


All Published Papers Search Service


A Novel Genetic Algorithm for Degree-Constrained Minimum Spanning Tree Problem


Lixia Hanr, Yuping Wang


Vol. 6  No. 7  pp. 50-57


A novel genetic algorithm is proposed for degree-constrained Minimum Spanning Tree (short for d-MST) problem in this paper. First, a novel model that transfer d-MST problem into a preference two objective MST problem is presented. Based on this model, a new crossover operator, a local search scheme, a mutation operator and a new selection operator are designed based on the preference of the two objectives. Then, a new genetic algorithm (short for GA) is proposed. Furthermore, the convergence of the proposed algorithm to globally optimal solution with probability one is proved. The simulation results indicate the proposed algorithm is effective.


degree-constrained minimum spanning tree, genetic algorithm, convergence