Razgon, Igor ;
O'Sullivan, Barry
Directed Feedback Vertex Set is Fixed-Parameter Tractable
Abstract
We resolve positively a long standing open question regarding the
fixed-parameter tractability of the parameterized Directed Feedback
Vertex Set problem. In particular, we propose an algorithm which
solves this problem in $O(8^kk!*poly(n))$.
BibTeX - Entry
@InProceedings{razgon_et_al:DSP:2007:1236,
author = {Igor Razgon and Barry O'Sullivan},
title = {Directed Feedback Vertex Set is Fixed-Parameter Tractable},
booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
year = {2007},
editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
number = {07281},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1236},
annote = {Keywords: Directed FVS, Multicut, Directed Acyclic Graph (DAG)}
}
|
Keywords: |
|
Directed FVS, Multicut, Directed Acyclic Graph (DAG) |
|
Seminar: |
|
07281 - Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
|
|
Issue date: |
|
2007 |
|
Date of publication: |
|
28.11.2007 |
28.11.2007
