Title :
A new approach to the degree-constrained minimum spanning tree problem using genetic algorithm
Author :
Zhou, Gengui ; Gen, Mitsuo ; Wu, Tianzu
Author_Institution :
Dept. of Ind. & Syst. Eng., Ashikaga Inst. of Technol., Japan
Abstract :
The degree-constrained minimum spanning tree problem is of high practical importance. Up to now there have been few effective algorithms to solve this problem because of its NP-hard complexity. In this paper we present an approach to solving this problem by using genetic algorithms (GAs), and provide numerical example to demonstrate the efficiency of the proposed approach
Keywords :
computational complexity; genetic algorithms; minimisation; trees (mathematics); NP-hard complexity; degree-constrained minimum spanning tree problem; genetic algorithm; Biological cells; Communication networks; Encoding; Genetic algorithms; Genetic engineering; Heuristic algorithms; Polynomials; Roads; Systems engineering and theory; Traveling salesman problems;
Conference_Titel :
Systems, Man, and Cybernetics, 1996., IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7803-3280-6
DOI :
10.1109/ICSMC.1996.561363
