Premium
A memetic algorithm for the weighted feedback vertex set problem
Author(s) -
Carrabs Francesco,
Cerrone Carmine,
Cerulli Raffaele
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21577
Subject(s) - feedback vertex set , memetic algorithm , vertex (graph theory) , algorithm , computer science , feedback arc set , mathematics , combinatorial optimization , metaheuristic , undirected graph , graph , set (abstract data type) , mathematical optimization , local search (optimization) , combinatorics , line graph , voltage graph , programming language
Given an undirected and vertex weighted graph G = ( V , E , w ) , the Weighted Feedback Vertex Set Problem consists of finding the subset F ⊆ V of vertices, with minimum weight, whose removal results in an acyclic graph. Finding the minimum feedback vertex set in a graph is an important combinatorial problem that has a variety of real applications. In this article, we introduce a memetic algorithm for this problem. We propose an efficient greedy procedure that quickly generates chromosomes with specific characteristics and a wise application of recent local search procedures based on k ‐diamonds. Computational results show that the proposed algorithm outperforms the effectiveness of two other metaheuristics recently proposed in the literature for this problem. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 339–356 2014