Polynomial kernels for deletion to classes of acyclic digraphs
type: Item
instance of: scholarly article
title: Polynomial kernels for deletion to classes of acyclic digraphs
zbMATH Open document ID: 1387.68137
author: Matthias Mnich
author: Erik Jan van Leeuwen
published in: Discrete Optimization
publication date: 2018-05-24T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5756/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6872137
zbMATH Keywords: directed feedback vertex set
zbMATH Keywords: kernelization
zbMATH Keywords: out-forest
MaRDI profile type: Publication
OpenAlex ID: W2593070308
cites work: Reducibility among Combinatorial Problems
cites work: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
cites work: Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Parameterized Algorithms
cites work: A cubic kernel for feedback vertex set and loop cutset
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)
cites work: Q4694754
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Packing directed circuits fractionally
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: Q4393480
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
cites work: A Polynomial Kernel for Proper Interval Vertex Deletion
cites work: On the completeness of a generalized matching problem
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Face covers and the genus problem for apex graphs
cites work: Q4198056
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
DOI: 10.1016/J.DISOPT.2017.02.002
description: scientific article; zbMATH DE number 6872137