The Hitting Set Problem and Evolutionary Algorithmic Techniques with ad-hoc Viruses (HEAT-V)

Vincenzo Cutello¹ and Francesco Pappalardo¹

Dept. of Mathematics and Computer Science
University of Catania
V. le A. Doria 6-I
95125 Catania, Italy
{cutello,francesco}@dmi.unict.it

Abstract. The Weighted Minimum Hitting Set Problem (WMHSP) and the standard Minimum Hitting Set Problem (MHSP), are combinatorial problems of great interest for many applications. Although, these problems lend themselves quite naturally to an evolutionary approach. To our knowledge, there are no significant results of evolutionary algorithms applied to either the WMHSP or the MHSP, except for the results contained in Cutello et al., (2002). We will now formally introduce the optimization problem and recall that the corresponding decision problem is -complete.

LNCS 2724, p. 1570 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003