Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

Matthias Mnich; Erik Jan van Leeuwen

doi:10.1016/j.disopt.2017.02.002

Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

Matthias Mnich^*, Erik Jan van Leeuwen

^*Corresponding author for this work

QE Operations research

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar

Original language	English
Pages (from-to)	48-76
Number of pages	29
Journal	Discrete Optimization
Volume	25
Issue number	C
DOIs	https://doi.org/10.1016/j.disopt.2017.02.002
Publication status	Published - Aug 2017

Keywords

directed feedback vertex set
Kernelization
Out-forest
Directed feedback vertex set
ALGORITHMS
FEEDBACK VERTEX SET
GRAPHS

Access to Document

10.1016/j.disopt.2017.02.002Licence: Free access - publisher

Cite this

@article{1021fa1006d34494965f0c76411b9242,

title = "Polynomial Kernels for Deletion to Classes of Acyclic Digraphs",

abstract = "We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar",

keywords = "directed feedback vertex set, Kernelization, Out-forest, Directed feedback vertex set, ALGORITHMS, FEEDBACK VERTEX SET, GRAPHS",

author = "Matthias Mnich and {van Leeuwen}, {Erik Jan}",

note = "no data used",

year = "2017",

month = aug,

doi = "10.1016/j.disopt.2017.02.002",

language = "English",

volume = "25",

pages = "48--76",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

AU - Mnich, Matthias

AU - van Leeuwen, Erik Jan

N1 - no data used

PY - 2017/8

Y1 - 2017/8

N2 - We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar

AB - We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar

KW - directed feedback vertex set

KW - Kernelization

KW - Out-forest

KW - Directed feedback vertex set

KW - ALGORITHMS

KW - FEEDBACK VERTEX SET

KW - GRAPHS

U2 - 10.1016/j.disopt.2017.02.002

DO - 10.1016/j.disopt.2017.02.002

M3 - Article

SN - 1572-5286

VL - 25

SP - 48

EP - 76

JO - Discrete Optimization

JF - Discrete Optimization

IS - C

ER -