A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem

Panos M. Pardalos, Tianbing Qian () and Mauricio G.C. Resende ()
Additional contact information
Panos M. Pardalos: University of Florida
Tianbing Qian: The University of Iowa
Mauricio G.C. Resende: AT&T Labs Research

Journal of Combinatorial Optimization, 1998, vol. 2, issue 4, No 8, 399-412

Abstract: 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 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.

Keywords: combinatorial optimization; feedback vertex set; local search; GRASP; probabilistic algorithm; computer implementation; heuristics; integer programming (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009736921890 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:2:y:1998:i:4:d:10.1023_a:1009736921890

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009736921890

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().