A greedy randomized adaptive search procedure for feedback vertex set

P. M. Pardalos, T. Qian, and M.G.C. Resende

J. of Combinatorial Optimization, vol. 2, pp. 399-412, 1999.

ABSTRACT

A Greedy Randomized Adaptive Search Procedure (GRASP) is a randomized heuristic that has produced high quality solutions for a wide range of combinatorial optimization problems.  The NP-complete Feedback Vertex Set (FVS) Problem is to find the minimum number of vertices that need to be removed from a directed graph so that the resulting graph has no directed cycle.  The FVS problem has found applications in many fields, including VLSI design, program verification, and statistical inference.  In this paper, we develop a GRASP for the the FVS problem. We describe GRASP construction mechanisms and local search, as well as some efficient problem reduction techniques.  We report computational experience on a set of test problems using three variants of GRASP.

PostScript file of full paper

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 25 June 2002

Copyright Notice