Kernels for deletion to classes of acyclic digraphs
type: Item
instance of: scholarly article
title: Kernels for deletion to classes of acyclic digraphs
zbMATH Open document ID: 1380.68207
author: Akanksha Agrawal
author: Saket Saurabh
author: Roohani Sharma
author: Meirav Zehavi
published in: Journal of Computer and System Sciences
publication date: 2017-11-14T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6777/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6806903
zbMATH Keywords: out-forest
zbMATH Keywords: pumpkin
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W2751689185
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
cites work: On Feedback Vertex Set New Measure and New Structures
cites work: Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
cites work: Improved algorithms for feedback vertex set problems
cites work: Q3549698
cites work: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Subset Feedback Vertex Set Is Fixed-Parameter Tractable
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Inapproximability of H-Transversal/Packing
cites work: Q5743513
cites work: Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
cites work: Faster deterministic \textsc{Feedback Vertex Set}
cites work: Faster fixed parameter tractable algorithms for finding feedback vertex sets
cites work: Half-integrality, LP-branching and FPT Algorithms
cites work: On Independent Circuits Contained in a Graph
cites work: Packing cycles through prescribed vertices
cites work: Packing directed cycles through a specified vertex set
cites work: Disjoint cycles intersecting a set of vertices
cites work: Packing directed circuits
cites work: Packing directed circuits fractionally
cites work: Packing circuits in eulerian digraphs
cites work: Fundamentals of parameterized complexity
cites work: Parameterized Algorithms
cites work: A kernelization algorithm for \(d\)-hitting set
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
cites work: A 4 k 2 kernel for feedback vertex set
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
DOI: 10.1016/J.JCSS.2017.07.008
description: scientific article; zbMATH DE number 6806903