Paper Info
Title
A Tabu search heuristic based on k-diamonds for the weighted feedback vertex set problem
Abstract
Given an undirected and vertex weighted graph G = (V,E,w), the Weighted Feedback Vertex Problem (WFVP) consists of finding a subset F ⊆ V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs is known to be NP-hard and to be polynomially solvable on some special classes of graphs (e.g., interval graphs, co-comparability graphs, diamond graphs). In this paper we introduce an extension of diamond graphs, namely the k-diamond graphs, and give a dynamic programming algorithm to solve WFVP in linear time on this class of graphs. Other than solving an open question, this algorithm allows an efficient exploration of a neighborhood structure that can be defined by using such a class of graphs. We used this neighborhood structure inside our Iterated Tabu Search heuristic. Our extensive experimental results show the effectiveness of this heuristic in improving the solution provided by a 2-approximate algorithm for theWFVP on general graphs.
Year
DOI
Venue
2011
10.1007/978-3-642-21527-8_66
INOC
Keywords
Field
DocType
special class,weighted feedback vertex set,general graph,tabu search heuristic,co-comparability graph,neighborhood structure,diamond graph,2-approximate algorithm,weighted feedback vertex problem,dynamic programming algorithm,vertex weighted graph,iterated tabu search heuristic
Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Chordal graph,Clique-sum,Pathwidth,Metric dimension,Trapezoid graph,Mathematics,Maximal independent set
Conference
Volume
ISSN
Citations 
6701
0302-9743
2
PageRank 
References 
Authors
0.37
12
4
Name
Order
Citations
PageRank
Francesco Carrabs119915.55
R. Cerulli225223.85
Monica Gentili316712.60
Gennaro Parlato449827.20