Lemaic, Mile and Speckenmeyer, Ewald
(2009).
Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem.
Working Paper.
|
PDF
zaik2010-596.pdf Download (168kB) | Preview |
Abstract
Let G be a directed graph. A vertex set F is called feedback vertex set (FVS) if its removal from G results in an acyclic graph. Because determining a minimum cardinality FVS is known to be NP hard, Karp72, one is interested in designing fast approximation algorithms determining near-optimum FVSs. The paper presents deterministic and randomised heuristics based on Markov chains. In this regard, an earlier approximation algorithm developed in Speckenmeyer89 is revisited and refined. Experimental results demonstrate the overall performance superiority of our algorithms compared to other algorithms known from literature with respect to both criteria, the sizes of solutions determined, as well as the consumed runtimes.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-549911 | ||||||||||||
| Date: | 2009 | ||||||||||||
| Language: | English | ||||||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||
| Subjects: | Data processing Computer science | ||||||||||||
| Refereed: | No | ||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54991 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |