Title :
An effective ant-based algorithm for the degree-constrained minimum spanning tree problem
Author_Institution :
Moscow State Univ., Moscow
Abstract :
The minimum spanning tree problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the degree-constrained minimum spanning tree problem. Finding the degree-constrained minimum spanning tree of a graph is a well-studied NP-hard problem. This paper presents an effective ant-based algorithm for the degree-constrained minimum spanning tree problem. Experimental results on a benchmark set of problem instances show that the algorithm performs very well against previous algorithms.
Keywords :
computational complexity; graph theory; optimisation; trees (mathematics); NP-hard problem; ant-based algorithm; degree-constrained minimum spanning tree problem; graph tree; Approximation algorithms; Cybernetics; Evolutionary computation; Heuristic algorithms; Iterative algorithms; Mathematics; NP-hard problem; Polynomials; Traveling salesman problems; Tree graphs;
Conference_Titel :
Evolutionary Computation, 2007. CEC 2007. IEEE Congress on
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-1339-3
Electronic_ISBN :
978-1-4244-1340-9
DOI :
10.1109/CEC.2007.4424510
