DocumentCode
2688728
Title
An effective ant-based algorithm for the degree-constrained minimum spanning tree problem
Author
Doan, Minh N.
Author_Institution
Moscow State Univ., Moscow
fYear
2007
fDate
25-28 Sept. 2007
Firstpage
485
Lastpage
491
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/CEC.2007.4424510
Filename
4424510
Link To Document