ALCOMFT-TR-01-165

M.J. Blesa, P. Moscato and F. Xhafa
A Memetic Algorithm for the Minimum Weighted k-Cardinality Tree Subgraph Problem"
Barcelona. Work packages 4 and 5. June 2001.

Abstract: In this paper we present a memetic algorithm for the minimum weighted k-cardinality tree subgraph problem. This problem consists in finding, in a given undirected weighted graph G=(V,E,W), a tree T of k edges having minimal total weight among all of k-trees that are subgraphs of G. This problem was first described by Hamacher, Jornsten, and Maffioli (1991) who also proved to be strongly NP-hard. Given this observation, researchers have focused on heuristic and metaheuristic algorithms to find suboptimal feasible solutions for the problem, as a good way to cope with most practical setting applications. To our knowledge, no memetic algorithm (MA) has yet been reported for this problem. It is known that some MAs have a good synergy with Tabu Search when they use it as individual steps for diversification and local optimization by the agents. As a consequence, one of our main motivations was to obtain a new implementation of an MA to the problem using an existing implementation of Tabu Search to the problem (Blesa and Xhafa, 2000). We are currently implementing the proposed algorithm.

Postscript file: ALCOMFT-TR-01-165.ps.gz (143 kb).