 |
    |
Ant System for the k-Cardinality Tree Problem
Thang N. Bui and Gnanasekaran Sundarraj
Department of Computer Science, The Pennsylvania State University at Harrisburg, Middletown, PA 17057tbui@psu.edu
gxs241@psu.edu
Abstract. This paper gives an algorithm for finding the minimum weight tree having k edges in an edge weighted graph. The algorithm combines a search and optimization technique based on pheromone with a weight based greedy local optimization. Experimental results on a large set of problem instances show that this algorithm matches or surpasses other algorithms including an ant colony optimization algorithm, a tabu search algorithm, an evolutionary algorithm and a greedy-based algorithm on all but one of the 138 tested instances.
LNCS 3102, p. 36 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004