Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem

Lemaic, Mile and Speckenmeyer, Ewald (2009) Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem.
Technical Report , 21 p.

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.


Actions:
Download: [img] Postscript
Download (405kB) | Preview
Download: [img] PDF
Download (168kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] 0 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • Uncontrolled Keywords: feedback vertex set, digraph, Markov chain, heuristics
    Subjects: 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Speckenmeyer
    Depositing User: Mile Lemaic
    Date Deposited: 08 Jan 2010 00:00
    Last Modified: 19 Dec 2011 09:44
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Mile Lemaic
    Date Deposited: 08 Jan 2010 00:00
    Last Modified: 19 Dec 2011 09:44
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/596